Can anybody tell the time complexity and space complexity for recursive approach?


  • 0
    X

    Is it O(n) for time and O(logn) for space?


  • 1
    M

    There are N elements in the array. The recursive approach creates N nodes for the tree.

    Space N nodes for N elements - O(N)
    Time N calls for N nodes - O(N)

    Although the recursion branches out to left and right by the power of 2, at the end of computation, N nodes have to be made, thus N calls to the recursive method.


  • 0
    S

    It's O(n) both in run time and space

    For run time, just consider how many times a particular number will be treated as a root->only once. So each number leads to a recursive call.

    For space, just follow up the run time, each number leads to a recursive call, each recursive call takes O(1) space, n recursive calls takes O(n) space.


Log in to reply
 

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