Would this algorithm run in O(n)?

问题:

Note: This is problem 4.3 from Cracking the Coding Interview 5th Edition

Problem:Given a sorted(increasing order) array, write an algorithm to create a binary search tree with minimal height

Here is my algorithm, written in Java to do this problem

  public static IntTreeNode createBST(int[] array) {
         return createBST(array, 0, array.length-1);
   }
   private static IntTreeNode createBST(int[] array, int left, int right) {
        if(right >= left) {
            int middle = array[(left + right)/2;
            IntTreeNode root = new IntTreeNode(middle);
            root.left = createBST(array, left, middle - 1);
           root.right = createBST(array, middle + 1, right);
            return root;
         } else {
             return null;
         }
    }

I checked this code against the author's and it's nearly identical.
However I am having a hard time with analyzing the time complexity of this algorithm.
I know this wouldn't run in O(logn) like Binary Search because you're not doing the same amount of work at each level of recursion. E.G at the first level, 1 unit of work, 2nd level - 2 units of work, 3rd level - 4 units of work, all the way to log₂(n) level - n units of work.

So based off that, the number of steps this algorithms takes would be upper bounded by this mathematical expression

which after watching Infinite geometric series, I evaluated to

or 2n which would be in O(n)

Do you guys agree with my work here and that this algorithm would run in O(n) or did I miss something or it actually runs in O(nlogn) or some other function class?

回答1:

Sometimes you can simplify calculations by calculating the amount of time per item in the result rather than solving recurrence relations. That trick applies here. Start by changing the code to this obviously equivalent form:

private static IntTreeNode createBST(int[] array, int left, int right) {
    int middle = array[(left + right)/2;
    IntTreeNode root = new IntTreeNode(middle);
    if (middle - 1 >= left) {
        root.left = createBST(array, left, middle - 1);
    }
    if (right >= middle + 1) {
        root.right = createBST(array, middle + 1, right);
    }
    return root;
}

Now every call to createBST directly creates 1 node. Since there's n nodes in the final tree, there must be n total calls to createBST and since each call directly performs a constant amount of work, the overall time complexity is O(n).

回答2:

If and when you get confused in recursion, substitute the recursive call (mentally, of course) as a loop. For example, in your above function, you can imagine the recursive calls to be inside a "while loop". Since, it is now a while loop executed till the time all n nodes are traversed, complexity is O(n).