1,935 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

0 votes
0 votes
Space complexity is the sum of stack space and size of input ... as you have n elements and assuming it is of 1 byte all n are of n B and log n is the stack space so n+ log n which will give order of n

Related questions

0 votes
0 votes
2 answers
1
dhruba asked Jun 5, 2023
1,094 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,058 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,945 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,361 views
Why to prefer binary search over ternary search?Can someone give recreance relation for ternary search,so that i can compare both