1 1 vote A binary search algorithm is implemented using recurrsion then what is the space and time complexity? Algorithms binary-search recursion space-complexity time-complexity + – A_i_$_h 851 views answer comment Share Follow Print See all 3 Comments 3 3 Comments reply joshi_nitish commented Jul 24, 2017 reply Follow flag both space and time complexity will be O(logn)... 2 2 replyShare Gaurav Joshi commented Jul 25, 2017 reply Follow flag 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 replyShare joshi_nitish commented Jul 26, 2017 reply Follow flag 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).... 2 2 replyShare Please log in or register to add a comment.
1 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 saxena0612 answered Jul 26, 2017 saxena0612 comment Share Follow 0 reply Please log in or register to add a comment.
