Time complexity, binary (search) tree

0
votes

assume I have a complete binary tree up-to a certain depth d. What would the time complexity be to traverse (pre-order traversal) this tree.

I am confused because I know that the amount of nodes in the tree is 2^d, so therefore the time complexity would be BigO(2^d) ? because the tree is growing exponentially.

But, upon research on the internet, Everyone states that's traversal is BigO(n) where n is the number of elements (which would be 2^d in this case), not BigO(2^d), what am I missing?

thanks

2
performancetime-complexityasymptotic-complexity
n = 2^d. There is no question here. - Mitch Wheat
if n = 2^d, then I can say either BigO(n) or BigO(2^d). if n is 2^d? - dgamma3
it is customary to use n. The problem size is expressed in terms of n, and so is the complexity. - Mitch Wheat

2 Answers

3
votes

n is defined as the number of nodes.

2^d is only the number of nodes when every possible node at that depth is full

ie.

     o
   /   \
  o     o
 / \   
o   o

only has 5 nodes when 2^d is 8

A complete binary tree has every node filled except for last row and all of the nodes are filled to the left. You can find the definition on wikipedia

http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

0
votes

Even if you can express the time complexity as O(2^d), that's pretty useless as it's not something that you can use to compare it to the time complexity of any other collection.

Expressing the time complexity as O(n) is on the other hand very useful. It tells you exactly how the collection reacts when you increase the number of items, without having to know exactly how the collection is implement, and you can compare it to the time complexity of other collections.