4

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

Community
  • 1
  • 1
Jim
  • 482
  • 1
  • 5
  • 20

1 Answers1

3

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)

Lucian Enache
  • 2,510
  • 5
  • 34
  • 59
amit
  • 175,853
  • 27
  • 231
  • 333
  • I think it should be clarified that the answer yes/no in the boolean array p directly correspond to the internal nodes numbered 0-m-1 for m questions asked and m answers in the array, with 0 being the root, so technically I can go back up the tree if the person answers yes to question no to question 0, the root, they go right, but this question could be internal node 3, hence the answer provided is p[3] not p[1] if you can follow that... I should have made an edit was just rereading my post now, i'll add that in – Jim Aug 27 '13 at 07:02
  • Also, could I trouble you for an edit on how this would change for a non balanced tree? – Jim Aug 27 '13 at 07:05
  • @Jim The point is you modify root and following it, you never go up - thus the complexity is `O(h)` as explained. If the tree is not balanced, then `h` could also be `n` - making it `Theta(n)`. – amit Aug 27 '13 at 07:07
  • 2
    Is the word "finite" correct? Shouldn't it be something like "constant"? – Honza Brabec Aug 27 '13 at 07:09
  • @amit Oh right i see... that is very insightful, I need to represent it in BigO not BigTheta but thank you very much for that, cause I was getting a bit confused – Jim Aug 27 '13 at 07:09