what's the time complexity of the following program?

2018-06-13 19:26:52

This question already has an answer here:

Big O, how do you calculate/approximate it? 22 answers

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'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

链接地址: http://www.djcxy.com/p/39362.html