CODEWITHSUNDEEP
time-complexitymultiplicationbig-o
CarolineRudolph
CarolineRudolph

Reputation: 101

Big-Theta: multiplying Theta(n) and Theta(n^2) = Theta(n^3)?

If f(n) = Θ(n) and

g(n) = Θ(n^2),

then f(n) * g(n) = Θ(n^3)?

Upvotes: 2

Views: 1346

Answers (1)

dfrib
dfrib

Reputation: 73236

Problem

Technically, Θ(n) is a set of functions, so we say that f is in Θ(n), rather than f(n) being equal to Θ(n).

Hence, the problem we want to investigate is:

Let 

h(n) = g(n) · f(n)                                           (*)

Does f ∈ ϴ(n) and g ∈ ϴ(n^2) imply that h ∈ ϴ(n^3)?

Preparations

Let's start by loosely stating the definition of Big-ϴ notation

f ∈ ϴ(g(n))

⇨ For some positive constants k1, k2, and n0, the following holds:

k1 · |g(n)| ≤ |f(n)| ≤ k2 · |g(n)|, for all n ≥ n0           (+)

We will make use of this definition below but assume, without loss of generality, that both f(n) and g(n) above are non-negative for all n.

Solution

From the above we can state, for some positive set of constants (c1, c2, n0) and (d1, d2, m0), that the following holds 

f ∈ ϴ(n):    c1 · n   ≤ f(n) ≤ c2 · n,   for all n ≥ n0        (i)
g ∈ ϴ(n^2):  d1 · n^2 ≤ g(n) ≤ d2 · n^2, for all n ≥ m0        (ii)

Now, the set of constants (c1, c2, n0) (as well as (d1, d2, m0)) is not unique; if such a set exists, an infinite number of such sets exist. Since f ∈ ϴ(n) and g ∈ ϴ(n^2) holds, such sets do exist, and we can, without loss of generality, assume that we can find a set of constants (c1, c2, n0) and (d1, d2, m0) such that c1=d1, c2=d2 and n0=m0 all hold. Hence, we can re-state (i-ii) as:

f ∈ ϴ(n):    c1 · n   ≤ f(n) ≤ c2 · n,   for all n ≥ n0        (I)
g ∈ ϴ(n^2):  c1 · n^2 ≤ g(n) ≤ c2 · n^2, for all n ≥ n0        (II)

for some set of positive constants (c1, c2, n0).

Now, since n > n0 > 0, all terms in the inequalities (I-II) above are positive, and we can apply (*) directly:

(I) * (II):

    c1^2 · n^3 ≤ f(n) · g(n) ≤ c2^2 · n^3, for all n ≥ n0      (iii)

Now, let k1 = c1^2 and k2=c2^2, and insert---among with h(n) = f(n) · g(n)---into (iii), yielding

    k1 · n^3 ≤ h(n) ≤ k2 · n^3, for all n ≥ n0                 (III)

This is, by (+), the very definition of h ∈ ϴ(n^3), and we have hence solved our problem by showing that:

For h(n) as in (*): f ∈ ϴ(n) and g ∈ ϴ(n^2) implies that h ∈ ϴ(n^3)

Upvotes: 3

Related Questions