Understanding Big(O) in loops

Question

I am trying to get the correct Big-O of the following code snippet:

s = 0
for x in seq:
  for y in seq:
    s += x*y
  for z in seq:
    for w in seq:
      s += x-w

According to the book I got this example from (Python Algorithms), they explain it like this:

The z-loop is run for a linear number of iterations, and it contains a linear loop, so the total complexity there is quadratic, or Θ(n²). The y-loop is clearly Θ(n). This means that the code block inside the x-loop is Θ(n + n²). This entire block is executed for each round of the x-loop, which is run n times. We use our multiplication rule and get Θ(n(n + n²)) = Θ(n² + n³) = Θ(n³), that is, cubic.

What I don't understand is: how could O(n(n+n²)) become O(n³). Is the math correct?

Answer 1

The math being done here is as follows. When you say O(n(n + n²)), that's equivalent to saying O(n² + n³) by simply distributing the n throughout the product.

The reason that O(n² + n³) = O(n³) follows from the formal definition of big-O notation, which is as follows:

A function f(n) = O(g(n)) iff there exists constants n₀ and c such that for any n ≥ n₀, |f(n)| ≤ c|g(n)|.

Informally, this says that as n gets arbitrary large, f(n) is bounded from above by a constant multiple of g(n).

To formally prove that n² + n³ is O(n³), consider any n ≥ 1. Then we have that

n² + n³ ≤ n³ + n³ = 2n³

So we have that n² + n³ = O(n³), with n₀ = 1 and c = 2. Consequently, we have that

O(n(n + n²)) = O(n² + n³) = O(n³).

To be truly formal about this, we would need to show that if f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)). Let's walk through a proof of this. If f(n) = O(g(n)), there are constants n₀ and c such that for n ≥ n₀, |f(n)| ≤ c|g(n)|. Similarly, since g(n) = O(h(n)), there are constants n'₀, c' such that for n ≥ n'₀, g(n) ≤ c'|h(n)|. So this means that for any n ≥ max(c, c'), we have that

|f(n)| ≤ c|g(n)| ≤ c|c'h(n)| = c x c' |h(n)|

And so f(n) = O(h(n)).

To be a bit more precise - in the case of the algorithm described here, the authors are saying that the runtime is Θ(n³), which is a stronger result than saying that the runtime is O(n³). Θ notation indicates a tight asymptotic bound, meaning that the runtime grows at the same rate as n³, not just that it is bounded from above by some multiple of n³. To prove this, you would also need to show that n³ is O(n² + n³). I'll leave this as an exercise to the reader. :-)

More generally, if you have any polynomial of order k, that polynomial is O(n^k) using a similar argument. To see this, let P(n) = ∑_i=0^k(a_inⁱ). Then, for any n ≥ 1, we have that

∑_i=0^k(a_inⁱ) ≤ ∑_i=0^k(a_in^k) = (∑_i=0^k(a_i))n^k

so P(n) = O(n^k).

Hope this helps!