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

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

commented: 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.

commented: 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?

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.