0

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

3
Contributors
4
Replies
5
Views
8 Years
Discussion Span
Last Post by sarehu
-1

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

Votes + Comments
Thanks for kind help.
-1

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

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?

0

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.