Computing time from complexity classes

Question

f has a complexity class O(N(logN)^2), for N = 1000 the program runs in 8 seconds

Compute how long it will take to run when N = 1,000,000

I computed the time to be 32000 seconds, however I am confused because N grew 1000 times but the time increased by 4000 times. I thought that since this is a log function the factor increase of N should be less than that of time.

Are my calculations wrong or is there something I am not understanding?

Answer 1

"since this is a log function": no, this is a linpolylog function. Because there is a linear factor N and a polylog one log^2(N), i.e. a polynomial of a logarithm.

So N grows by a factor 1000 and log(N) by a factor 2 (undisputably smaller than 1000) thus log^2(N) by a factor 4, for a total factor 4000.

Answer 2

Your calculations are correct. N(logN)^2 grows a little faster than N does. Indeed, N factors both complexities but (logN)^2 is crescent and unbound and so bigger than a constant reaching a big enough input.