CODEWITHSUNDEEP
javaalgorithmbig-o
Jim
Jim

Reputation: 482

Understanding Big O notation derived from code

I wrote some code for some binary tree sets of problems... the code is as follows it keeps going down the tree left for an answer yes, and right of an answer no and returns the external node if it arrives at one.

Written in java,

public static int price(BinaryTree<Integer> t, boolean[] p) {

    Position<Integer> root = t.root(); //1
    while (t.isInternal(root)) { //2

        int element = root.element();  // 3

        if (!p[element]) { //4
            root = t.getRight(root);//5
        }

        if (p[element]) { //6
            root = t.getLeft(root); //7
        }
    }
    int price = root.element(); //8
    return price; //9
}

When calculating the Big O I thought it best to number the steps of code in the comments as above...I followed the example from here

Big O, how do you calculate/approximate it?

So above 1-9 should equate to something like this, where C are constants and ??? are my loops (Where N is the number of inputs for a given data structure)

C + ??? + C + ??? + C + ??? + C + C + C

My while loop is I think C*N or (O(N)) rather but C*N for now) and my two if statements should be (For time complexity O(1) for indexing... and O(N) for space complexity, I'll stick with time complexity for now)

So now I should have(removing C elements cause they are constants and don't really matter)

C*N + C + C for time complexity

and

C*N + C*N + C*N for space complexity

Meaning I have

C*N or O (N) for time complexity and for space complexity

O(3N) which can be deemed O(N)...

So my question is, have I done this correctly, and if not where have I gone wrong?

Thank you

EDIT:

The tree moves left provided a true(yes) answer or right given a no. Internal nodes are numbered 0 through m-1 for m internal nodes in the tree. Hence if a no is given at the root, internal node 0, and therefore moves right, this internal node might be node 3, hence the boolean answer is at p[3] not p[1] as p[1] is the answer for node 1, i.e. question 1. Apologies for confusion

Upvotes: 4

Views: 655

Answers (1)

amit
amit

Reputation: 178441

Yes and no.

The algorithm is indeed O(n), because you "touch" each element not more then a constant number of times.

However, this is not a strict bound, or in other words - it is not Theta(n), it is Theta(logN). (Remember that big O is an upper bound only).

This is because the tree is balanced, and your algorithm is basically getting a path from the root to some leaf in the tree. Note that once you "chose" to go left/right, you never go back. So basically you "touch" a node in each height only a constant number of times, making your algorithm O(h) - where h is the height of the tree.

Since the tree is balanced, h < C * log(n), for some constant C - which makes the algorithm Theta(logN)

Upvotes: 3

Related Questions