Clever Geek Handbook

What is the time complexity of recursive traversal of a binary tree order

In THIS link geeksforgeeks they describe the time complexity of recursive order traversal O(n^2)

.

Time complexity: O(n^2)

worst case. For a skewed tree, it printGivenLevel()

takes O(n)

time, where n is the number of nodes in the skewed tree. So the time complexity printLevelOrder()

is O(n) + O(n-1) + O(n-2) + .. + O(1)

equal to O(n^2)

. This is not clear to me.

Can someone please help me understand.

+3


source to share


2 answers


For a warped tree:

1
 \
  2
   \
   ...
     \
      N

The depth of this tree is N, so the bottom function will run from 1 to N,

printLevelorder(tree)
for d = 1 to height(tree)
   printGivenLevel(tree, d);

I.e



printGivenLevel(tree, 1);
printGivenLevel(tree, 2);
...
printGivenLevel(tree, N);

And it printGivenLevel(tree, depth)

takes O (depth) time since it starts at the root every time.

Time complexity:

O(1) + O(2) + ... + O(N) = O(N^2)
+2


source


Sure.

Note that this is an arithmetic progression. We know it will add up like this:

n + (n - 1) + (n - 2) + ... + 1 = n * (n - 1) / 2

But:

n * (n - 1) / 2 = (n^2 - n) / 2

However, we know that the quadratic (quadratic) term dominates the expression over the linear term and that it 1 / 2

is a constant factor, both of which simplify the expression as follows:



First remove the constant factor:

O((n^2 - n) / 2) = O(n^2 - n)

Then keep the dominant term:

O(n^2 - n) = O(n^2)

This is how you achieve this complexity.

+1


source






More articles:


All Articles