CODEWITHSUNDEEP
algorithmtimetime-complexity
Beast
Beast

Reputation: 629

Time complexity calculation of algorithm

What is the complexity of the below program:

void function(int n)
{
int i, j, k , count =0;
for(i=n/2; i<=n; i++)
  for(j=1; j=j + n/2<=n; j++)
      for(k=1; k<=n; k= k * 2)
         count++;
}

Now as per my understanding the outer loop executes n/2 times. Inner loop executes n/2 times and third inner loop executes the log n times. Now if we denote the time complexity of algorithm as a function T(n).

T(n)=n/2n/2log n =n^2/4*log n

Now for very large input size of n term log n becomes too small in comparison with the term n^2. So per my understanding the time complexity of the algorithm must be O(n^2). But I have checked the answer of this above program it says the answer is O(n^2logn).

Why can't we ignore the term log n for larger values of n? Or is the calculation I have done wrong?

Upvotes: 1

Views: 1881

Answers (2)

Everettss
Everettss

Reputation: 16059

If we make assumption that your algorihtm has got running time function (is not exactly true):

T(n)=n/2*n/2*log n =n^2/4*log n= an^2*log(n)

You can do formal asymptotic analysis:

enter image description here

We can easily proof that we can find c1 and c2 to fulfill:

enter image description here

So finally you can say that your algorithm has got complexity:

enter image description here

Upvotes: 0

axiac
axiac

Reputation: 72376

You can ignore only the constant values. If n increases, log(n) also increases.

Upvotes: 3

Related Questions