In worst case n-1 levels with each level cost n so total cost = n *n= O(n2)
Can we do this way:
T(n) - T(n-1) = T(n/2)+n
meaning for one line we need T(n/2)+n time.
Using Master's theorem we got one Theta(n). So for n lines it will be n*Theta(n) = Theta(n2)
Check the link https://drive.google.com/file/d/0B2zVzfkXsyqfYl9hODBXdklxcFE/view
I am also getting same answer that the complexity is O(n*(3/2)n)
we can say O(n*2n)
If you check the link, the approach is totally difference. But I do not know whether it is correct or not
Link : https://drive.google.com/file/d/0B2zVzfkXsyqfYl9hODBXdklxcFE/view
I used Back substitution method for solving this particular problem. you can see the attached image.
The answer according to my approach is O(n^2).
EDIT- in the below image,read f(n) = n(n+1)/2 (in last third line)
Check the link
X->YZ , Y->XZ , ...