CODEWITHSUNDEEP
algorithm
janitha chanuka
janitha chanuka

Reputation: 103

Best and worst case running time of an algorithm

I need to calculate the best and worst case running time of following algorithm. My matter is do I need to consider i*i in second loop? And to get the complexity of that loop as Q(N^2)?

    for i=1 to 2*n do
       for j=1 to i*i do
          for k=1 to k<j do
             if j%i==0 then
                 sum=sum+1;

this is the full code

    procedure proc(n:integer){
    var i,j,k :integer
    var sum: integer
   begin
 sum=0;
 for i=1 to 2*n do
 begin
       for j=1 to i*i do
       begin 
              for k=1 to k<j do
              begin
                       if j%i==0 then
                       sum=sum+1;
                       end if
                       k=k+1;
    end
   j=j+1;
  end 
 i=i+i;
 end
 end }

Upvotes: 0

Views: 244

Answers (1)

amit
amit

Reputation: 178431

Let's analyze it from inside out.

         if j%i==0 then
             sum=sum+1;

This takes constant time every time it is reached.

      for k=1 to k<j do

The most inner loop runs O(j) times, once for each value of k from 1 to j (exclusive). So far we have O(j*1) = O(j)

   for j=1 to i*i do

For the middle loop - each value of j has to do job in the complexity of O(j). This means, you are going to need for this entire loop (for each value of i):

1 + 2 + .... + i*i = i*i*(i*i+1)/2 = i^2(i^2+1)/2  [sum of arithmetic progression]

The above is in O(i^4)

for i=1 to 2*n do

Sum{i^2*(i^2+1)/2 | i from 1 to 2n } which is in O(n^5)

Upvotes: 2

Related Questions