Understanding the Big O Note Derived from Code

Question

I wrote some code for some sets of binary problem sets ... the code is as follows, it continues to go down the tree to the left for the answer yes, and to the right of the answer no and returns an external node if it arrives on 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 Big O, I thought it was best to specify the code steps in the comments as above ... I followed the example from here

Big O, how do you calculate / approximate it?

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

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

My while , I think C*N or (O(N)) more likely, but C*N is for now), and my two if should be (for the time complexity of O(1) for indexing ... and O(N) for space complexity, I will adhere to time complexity at the moment)

So now I need (removing C elements, because they are constants and don't really matter much)

C*N + C + C for time complexity

and

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

Meaning I

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

O(3N) , which can be considered O(N) ...

So my question is: did I do it right, and if not, where did I go wrong?

thanks

EDIT:

The tree moves to the left if there is a true (yes) answer or to the right if it is not. Internal nodes are numbered from 0 to m-1 for m internal nodes in the tree. Therefore, if a no is specified in the root, the internal node 0 and, therefore, moves to the right, this internal node can be node 3, so the logical answer is in p [3], not p [1], since p [1] - answer for node 1 i.e. Question 1. Apologies for the confusion

Answer 1

Yes and no.

The algorithm is really O(n) , because you “touch” each element no more than a constant number of times.

However, this is not a strict binding, in other words, it is not Theta(n) , it is Theta(logN) . (Remember that large O is only the upper bound).

This is because the tree is balanced, and your algorithm basically gets the path from the root to some leaf in the tree. Please note that once you have "chosen" to go left / right, you will never return. Thus, basically you “touch” a node at 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 Theta(logN) algorithm does