Dark Mode

Asim Abbas
asked
in Programming
Jan 12, 2018

652 views
3 votes

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.

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.

"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.

0

@Asim

Space complexityis 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,

0

–1 vote

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.

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.

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

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

0