Time complexity of the following algorithms

[ChPravin]

hello all,

can someone help me in calculating the time complexities of the following algorithms:

1) for i ← 1 to n^2
for j ← i to i^3
k ← k + 1

2) i ← n
while i > 0
for j ← 1 to i^2
x ← (x + j)/2
i ← ⌊i/2⌋

the trouble I am facing in the above algos while calculating time complexity is that i am unable to relate the inner loop running time with respect to n.

Please reply asap.

Thanks & Regards

[sarehu]

You can probably find worst-case numbers though, using some comparisons to simpler equations.

[ithelp]

innermost loop for j can run from 1 to n^6 , hence you have got a O(n^6) algorithm.

[ChPravin]

Thanks for the reply.I got the first one,its O(n^8);O(n^2) for outer loop and O(n^6) for the inner loop.Any ideas on the second one?

[sarehu]

Your solution for the first is wrong. The inside of your inner loop is O(1), the outside of your inner loop is O(n^3), the inside of your outer loop is the same, O(n^3), and the outside of the outer loop, since it runs the inner loop n^2 times, is O(n^2*n^3) which is O(n^5).