If someone wants to generates a complete binary tree. This tree has h levels where h can be any positive integer and as an input to the algorithm. What complexity will it lie in and why?

CodePudding user response：

A complete binary tree is tree where all levels are full of nodes except the last level, we can define the time complexity in terms of upper bound.

If we know the height of the tree is h, then the maximum number of possible nodes in the tree are 2^h - 1.

Therefore, time complexity = O(2^h - 1).

To sell your algorithm in the market, you need tight upper bounds to prove that your algorithm is better than the others'.

A slightly tight upper bound for this problem can be defined after knowing exactly how many nodes are there in the tree. Let's say there are N.

Then, the time complexity = O(N).