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

8 Years
Discussion Span
Last Post by sarehu

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

Votes + Comments
Thanks for kind help.

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

Votes + Comments
No need to do people's homework for free.

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?


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).

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.