1 votes 1 votes 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 asked Jul 24, 2017 • retagged Jun 23, 2022 by makhdoom ghaya A_i_$_h 411 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply joshi_nitish commented Jul 24, 2017 reply Follow Share both space and time complexity will be O(logn)... 2 votes 2 votes Gaurav Joshi commented Jul 25, 2017 reply Follow Share 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 votes 0 votes joshi_nitish commented Jul 26, 2017 reply Follow Share 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 votes 2 votes Please log in or register to add a comment.
1 votes 1 votes 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 See all 0 reply Please log in or register to add a comment.
