algorithmruntimebig-otime-complexityprocedure

How to find the running time of a specific procedure?

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.

Solution

  • 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 decrement 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.