Time complexity calculation of algorithm

Question

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?

Yes, log(n) is smaller than polynomial, but when it's multiplied it's still a factor. O(log(n)) is slower than O(n), but O(nlogn) is a thing, and it's similar to what you've got. O(nlogn) != O(n). A graph could illustrate this well. — keyser
– keyser, Commented Nov 22, 2014 at 17:38
Thanks keyser. Say for example if we have time complexity T(n)=n^3+n^2+n then for very large values of n we ignore the term n^2 and n then why can't we do the same thing over here ? — Beast
– Beast, Commented Nov 22, 2014 at 17:41
Yes, we do, because they're separate. Asymptotically the other ones won't have any notable impact, but asymptotically, O(nlogn) grows faster than O(n), since log(n) is more than a constant. I liked benji's illustration of how they're removed. — keyser
– keyser, Commented Nov 22, 2014 at 17:42
n^3 + n^2 is less than n^3 + n^3 = 2*n^3 which is O(n^3) — benji
– benji, Commented Nov 22, 2014 at 17:43

axiac · Accepted Answer · 2014-11-22 17:38:04Z

3

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

answered Nov 22, 2014 at 17:38

axiac

73.4k11 gold badges120 silver badges150 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Beast Over a year ago

Thanks axiac. But say for example if we have time complexity T(n)=n^3+n^2+n then for very large values of n we ignore the term n^2 and n then why can't we do the same thing over here ?

Everettss Over a year ago

@Beast You can ignore n^2 and n because you add them to n^3 not multiply like in your example.

Everettss · Accepted Answer · 2014-11-22 18:20:06Z

0

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

answered Nov 22, 2014 at 18:20

Everettss

16.2k9 gold badges78 silver badges106 bronze badges

Collectives™ on Stack Overflow

Time complexity calculation of algorithm

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related