Kindly see printallthelevels function at line 96 of the code how the worst case complexity is O(n square).
How the complexity of printlevel function is O(n square)
hi @ujj1804_1156aee80205d0bf,
the worst case height of a tree can be n and each time you are printing it level by level
1 + 2 + 3 … n = O(n2)
Sir i have understood that the maximum height can be N in case of a skewed binary tree , but can u explain that how the complexity of printlevel function at line 74 of code is O(n)?
@ujj1804_1156aee80205d0bf,
to print 1 level it takes O(n) time where n is the number of nodes in the skewed tree. So time complexity of print all level is O(n) + O(n-1) + O(n-2) + … + O(1)
which finally results in n2 also
for(int i=1;i<=level;i++)
{
**printlevel(root,i);**
cout<<endl;
}
Sir do you mean that for eg to print the first level the printlevel function does 1 operation that is print the node , to print the second level it makes 2 recursive calls to reach that level and print the nodes and so on
O(1) +O(2)+…O(n) = n2 ?
but all this is occuring inside a for loop so should not the complexity be n3
@ujj1804_1156aee80205d0bf no its included, let’s take the worst case of that also to understand.
you want to print the last level every time (in for loop) the loop can go to O(N) in case of skewed tree and for printing also you need O(N). as it is nested to it will be O(N*N)
Ok so as we have counted for each level like O(1) +O(2)+…+O(n) means the for loop is included right?
Sir one more thing that , why we consider a skewed binary tree in worst case ?
If we have a full binary tree lets say , more time will be taken to print this tree than skewed tree
Because when no. of nodes is same , the height of skewed binary tree is more?
thank u sir for helping me
