in Algorithms retagged by
173 views
1 vote
1 vote
A binary search algorithm is implemented using recurrsion

then what is the space and time complexity?
in Algorithms retagged by
by
173 views

3 Comments

both space and time complexity will be O(logn)...
2
2
In my opinion the space complexity is O(n).

space complexity= input space + extra space(stack space in case of recursion)

                           = n +logn

                           =O(n)
0
0
No, space complexity will b O(logn) only..
Space complexity= space required other than provided input+ depth of recursion tree..
Now,
Space required other than provided input= O(1) and depth of recursion tree=O(logn)...
Therefore overall space complexity=O(1)+O(logn)=O(logn)....
1
1

1 Answer

1 vote
1 vote

Most of the answers on the web are based on simple calculations that is they do not consider the stack space as in the space complexity. Thus ! it would be log(n) for both if you consider stack space and O(1) if you do not consider the stack space.

fo refernce :

https://en.wikipedia.org/wiki/Binary_search_algorithm

Related questions

1 vote
1 vote
1 answer
1
2 votes
2 votes
1 answer
4