1,932 views
6 votes
6 votes
How to get space complexity of binary search ..

I am getting confusion in

Space complexity = ip + extra (stack)

And ip = nB ( why it is nB) ?????

And extra = logn B

So

nB+ log n B = O(n) ...

5 Answers

Best answer
3 votes
3 votes
when we calculate space complexity then we consider only auxilary space taken by an algo. It's because input space will remain same for all algorithms.
for B.S  recurrence relation is T(n) = T(n/2) + 1 so space complexity and time complexity both will be same as in worst case there can be logn recursive calls.

PS: I don't know what does this 'B' ,mean
selected
1 votes
1 votes
space complexity for recursive is O(logn)

and for iterative it is O(1)

for recursive - you make recursive call every time when the array is half. At worst the the element could be present at the end and you have to call the function O(log n) times.

for iterative - creating a variable which will have index of middle. It will take O(1).
edited by
1 votes
1 votes
Bcz we take n inputs (generally).... An array of  n elements... To store those n elements sPace is needed
0 votes
0 votes
Here B represents Byte.. Whenever we talk about space complexity it will be input + extra  now input will be n Bytes however ip will be taken constant because it will be same for all algorithm therefore space complexity directly rely on #of recursive calls that is log n..

Related questions

0 votes
0 votes
2 answers
1
dhruba asked Jun 5, 2023
1,089 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...
0 votes
0 votes
1 answer
2
Sabir Khan asked Aug 8, 2018
1,056 views
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is(A) (n)(B) (logn)(C) (log*n)(D) (1)
3 votes
3 votes
1 answer
3
iarnav asked Mar 13, 2018
1,938 views
The average successful search time taken by binary search on a sorted array of 5 CONSECUTIVE integers starting with 1?My Answer is - 2.2Kindly tell me is it correct or no...
3 votes
3 votes
2 answers
4
rahul sharma 5 asked Mar 8, 2018
2,359 views
Why to prefer binary search over ternary search?Can someone give recreance relation for ternary search,so that i can compare both