How to find the running time of a specific procedure?

Question

For each of the procedures below, let T (n) be the running time. Find the order of T (n) (i.e., find f(n) such that T (n) ∈ (f(n)).

Procedure Fum(int n):

for i from 1 to n do    
 y ← 1/i
 x ← i
 while x > 0 do    
  x ← x − y 
 end while
end for

I know how to find run times of simple functions but since this is a nested loop where the inner loop depends on a variable from the outer loop, I'm having trouble.

Answer 1

It should be 1+4+9+...+n^2 = n(n+1)(2n+1)/6, or simply O(n^3), for this case.

For each step in the for-loop, it will run i^2 times for the while. Given x=i;y=1/i;, it will take i^2 (as x=y*i^2) times for x to reach x<=0 by decreament step x=x-y.

For i, it will be 1,2,...,n, summing them up, you will get 1+4+9+...n^2 = n(n+1)(2n+1)/6.

Answer 2

First, lets consider the runtime of the inner loop: We want to figure out how many times the inner loop runs, in terms of i. That is, we want to solve for f(i) in x-f(i)y = 0. If we sub in x = i, and y = 1/i, we get f(i) = i^2.

We know the outer loop will run exactly n times, so then, we get the total number of times the inner loop will be run:

= 1 + 4 + 9 + ... + n^2

This sum is equal to n(n+1)(2n+1)/6, which is O(n^3)