Big O notation g(n) ∈ O(f(n)) =⇒ (g(n))^2 ∈ O((f(n))^2)

user_10998152 0
Viewed 139

My question is, is this True.

g(n) ∈ O(f(n)) =⇒ (g(n))^2 ∈ O((f(n))^2)

At the long run it should be true, but i have one example (log n )^ 2 which is still in or less then O(sqrt n)

Is there a way to proof this without the graph.

THX

big-o
1 Answers

It is quite intuitive that, if a function g is less or equally fast than another function f, the square of g is less or equally fast than the square of f.

Formally:

  • Statement #1. g(n) ∈ O(f(n)) means that, for at least one choice of a constant k > 0, you can find a constant a such that the inequality 0 ≤ g(n) ≤ k f(n) holds for all n > a.
  • Statement #2. g(n)^2 ∈ O(f(n)^2) means that, for at least one choice of a constant k > 0, you can find a constant a such that the inequality 0 ≤ g(n)^2 ≤ k f(n)^2 holds for all n > a.

Since we want to prove that g(n) ∈ O(f(n)) implies g(n)^2 ∈ O(f(n)^2), we want to reach the statement #2 starting from the statement #1.

Let us take two constants k and a such that the statement #1 is satisfied.

First, notice that:

  • 0 ≤ k f(n) holds for all n > a (from hypotesis);
  • ⇒ 0 ≤ f(n) holds for all n > a (since k > 0). [Result #1]

Also notice that:

  • g(n) ≤ k f(n) holds for all n > a (from hypotesis);
  • ⇒ g(n)^2 ≤ (k f(n))^2 holds for all n > a (since, from hypotesis and result #1, both g(n) and f(n) are non-negative for all n > a, so we can keep the ≤ sign);
  • ⇒ g(n)^2 ≤ k^2 f(n)^2 holds for all n > a. [Result #2]

From results #1 and #2, the statement #2 is satisfied.

Q.E.D.

user_46077330
Related