Would this function be O(n^2log_2(n))?

Question

So I am given a function like 65536 n² + 128 n log₂n

and the only way that this would be O(n² log₂n) is if

C = 65664, n0 = 2 for all n ≥ 2 since

C1 = 65536 n1 = 2 when 65536 ≤ C1*n² and
C2 = 128 n2 = 1 when 128 ≤ C2*n

but the number I've chosen for the constant seems a bit to high, is there a way to check this?

Answer 1

O(65536 n² + 128 n log₂n) is the same as O(n² + n log₂n) since you can ignore multiplicative constants. O(n² + n log₂n) is equal to O(n²) since n² grows faster than n log₂n.

Also, by the way, the base of logarithms doesn't matter in Big-O analysis. All logarithms grow at the same rate. After all, log₂n = log n / log 2, and multiplicative constants can be factored out. You can simply say log n instead of log₂n.

Caveat: Technically, it is actually a true statement to say that 65536 n² + 128 n log₂n ∈ O(n² log₂n) because Big-O gives an upper bound, but not a strict one. O(n²) is a lower upper bound, if that makes sense.

That said, you should not have come up with O(n² log₂n). That was merely the result of accidentally turning an addition into a multiplication. As a rule of thumb, if you have multiple things added together inside a Big-O formula, you just have to figure out which one of them grows the fastest and then discard the others.

Answer 2

let's simplify the equation here since the constants don't really matter:

n² + n log₂n

since n² > n log₂n as n approches infinity

the Big-O is O(n²) as n² is the upper bound.