-1

what's the time complexity of the following program? How to calculate the complexity? What is the upper bound and lower bound of complexity?

for(i=n;i<=n^2;i++)
   for(j=1;j<=i*log(i);j++)
      a[i][j]+=3*i*j;
Sergey Grinev
  • 34,078
  • 10
  • 128
  • 141
Jason Walker
  • 1
  • 1
  • In the inner loop, you should increment `j` rather than `i`, or you'd get a crash when `i` finally wraps. – Daniel Fischer Jan 17 '12 at 01:10
  • Agreed: [cstheory](http://cstheory.stackexchange.com/questions/9771/whats-the-time-complexity-of-the-following-program-how-to-calculate-the-comple) – xikkub Jan 17 '12 at 04:57
  • @JasonWalker What's your calculation of the complexity classes? – Marcin Apr 05 '12 at 10:10

2 Answers2

0

In your outer loop, you're going from n->n^2, which is (n^2-n) iterations which is O(n^2).

In your inner loop, you're going from 1->approx (n^2)log(n^2) which is O((n^2)log(n))

a[i][j]+=3*i*j; is O(1), so you it doesn't contribute.

Putting it together, you have O(n^2 * n^2 * log(n)), which is O(n^4 log(n))

Mike T
  • 4,747
  • 4
  • 32
  • 52
0

Mike's answer is correct, just expanding steps in a different way

Inner loop : const * i*log(i) Outer loop : Sum(i over 1:n^2) of const * i * log(i)

O(algo) = O(Sum(i over 1:n^2) of i * log(i))

From http://en.wikipedia.org/wiki/Summation we find out that

Sum (i over 1:m) of (i * log(i)) = Theta(m^2*log(m))

Substitute m = n^2 we get

O(algo) = O(n^2)^2 log(n^2) = O(n^4)log(n) (eliminate 2) (Actually that is theta of algo)

EDIT: I just noticed outer loop is i over n:n^2, however answer is same

Om Deshmane
  • 808
  • 6
  • 11