CODEWITHSUNDEEP
algorithmtime-complexitycomputer-science
Roman.M
Roman.M

Reputation: 13

How is complexity of the following algorithm calculated?

int find_c(int n)
int i,j,c
   for(i=1; i < 2*n; i=i*3)
      for(j=400; j > 1; j--)
      c++
   for(i=c; i > 0; i--)
      if(even(i/3))
   for(j=n; j < n*n; j++)
      c++
   else
      for(j=1; j < 900; j=j*3)
      c++ 
   return c

I have this algorithm which is written in java and i need to find it's complexity depending on the input parameter n in worst case scenario. I can understand the basics of this procedure in which each loop has to be viewed separately. The complexity of this algorithm should be n2 log n but i can't understand how it is calculated. Can someone please explain this to me ?

Upvotes: 1

Views: 68

Answers (1)

Henry
Henry

Reputation: 43798

Since this is some kind of excercise, I will just show some parts and let the rest for you. In particular look at this code:

if(even(i/3))
    for(j=n; j < n*n; j++)
        c++
else
    for(j=1; j < 900; j=j*3)
        c++

From the loop enclosing this we know that even(i/3) will be true approximately in half of the executions, so the then and the else part contribute in the same amount to the runtime.

Lets look now at the then part: j will run from n to n*n so order of O(n * n). The statements in the body of the loop have a runtime of O(1), so all together O(n * n).

The loop in the else part on the other hand will execute log3(900) times which is a constant and the runtime of the body is constant as well. So this loop will in total contribute a runtime of O(1).

In total we get therefore for the whole if a runtime of O(n * n) + O(1) which is just O(n * n).

Upvotes: 1

Related Questions