In THIS geeksforgeeks link they are describing the time complexity of recursive level order traversal as O(n^2).
Time Complexity: O(n^2) in worst case. For a skewed tree, printGivenLevel() takes O(n) time where n is the number of nodes in the skewed tree. So time complexity of printLevelOrder() is O(n) + O(n-1) + O(n-2) + .. + O(1) which is O(n^2).This is not clear to me.
Can someone please help me understand.
For a skewed tree like this:
1
\
2
\
...
\
N
The depth of this tree is N, so the below function will run from 1 to N,
printLevelorder(tree)
for d = 1 to height(tree)
printGivenLevel(tree, d);
That is,
printGivenLevel(tree, 1);
printGivenLevel(tree, 2);
...
printGivenLevel(tree, N);
And printGivenLevel(tree, depth) takes O(depth) time since it begins from the root every time.
The time complexity is:
O(1) + O(2) + ... + O(N) = O(N^2)
Sure.
Notice that this is an arithmetic progression. We know that it will sum as follows:
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 (squared) term dominates the expression compared to the linear term and that the 1 / 2 is a constant factor, both of which simplify the expression as follows:
First, drop the constant factor:
O((n^2 - n) / 2) = O(n^2 - n)
Next, keep the dominant term:
O(n^2 - n) = O(n^2)
This is how you arrive at this complexity.
