Algorithms

Question

I am having a doubt in this question.

The binary search algorithm is implemented using recursion. Then the space complexity is :-

(1) O( 1 )

(2) O( n )

(3) O( logn )

(4) O(n logn )

According to me, the answer should be option 2.

Please explain the solution as well.

Comments

input space is not considered in space complexity, instead auxiliary space is counted.

---

"input space is not considered in space complexity, instead auxiliary space is counted" -> Can you please provide any verified source for your statement. 

Bcoz till now I was usnig this concept :-

Auxiliary Space is the extra space or temporary space used by an algorithm.

Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.

---

@Asim 

Space complexity is a function describing the amount of memory (space) an algorithm takes in terms of the amount of input to the algorithm. We often speak of "extra" memory needed, not counting the memory needed to store the input itself.

Reference: https://www.cs.utexas.edu/users/djimenez/utsa/cs1723/lecture2.html

Kindly read some textbooks for concepts rather than arguing on the basis of wrong concepts and confusing other users,

Answer 1

As question is talking about space complexity of binary search algo it would be O(1). it dosen't take any extra space to perform search because we have to apply Binary search algo on given input of array with distinct and sorted elements.

 

Space Complexity refers to the magnitude of auxiliary space your program takes to process the input. That is after main() how much extra space it is taking.

Comments

At each failure of comparison, a recursive call is made of of size n/2. Size of each subarray needs to be stored in the activation record of stack. Other wise there is no way of calculating middle element for comparison with the required element. So compulsory stack is needed.

And assuming this statement "Space Complexity refers to the magnitude of auxiliary space your program takes to process the input. That is after main() how much extra space it is taking"  to be true, then space complexity will be O(logn).

But my doubt is only about your statement for space complexity. Can you please provide the authenticity of you statement. Any resource, web link, snapshot , anything , so that my doubt will b cleared forever. Thanks in advance