The 1st approach (Binary search DFS) is linear on average, not Nlog(N).


  • 0
    I

    Re: [3 ways implemented in JAVA: Binary Search](in-order iterative & recursive)
    T(n) = T(n/2) + O(n) = T(n/4) + O(n/2) + O(n) = T(n/8) + O(n/4) + O(n/2) + O(n) = ... = O(n + n/2 + n/4 + n/8 + ...) = O(2n) = O(n)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.