Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 log2(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

enter image description here

which after watching Infinite geometric series, I evaluated to enter image description here

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?

like image 868
committedandroider Avatar asked May 29 '15 05:05

committedandroider


2 Answers

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).

like image 50
Paul Hankin Avatar answered Oct 25 '22 16:10

Paul Hankin


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).

like image 30
Tejash Desai Avatar answered Oct 25 '22 16:10

Tejash Desai