Question

Using the definition of Θ notation, prove that (3n + 13)(7n + 2)(log(1024n² + 100)) ∈ Θ(n²logn).

Answer 1

By definition of big-Theta (Θ):

f(n) = Θ(g(n)) iff there are three positive constants c₁, c₂ and n₀ such that

c₁|g(n)| ≤ |f(n)| ≤ c₂|g(n)| for all n ≥ n₀ -------------------------- (i)

Here f(n) = (3n + 13)(7n + 2)(log(1024n² + 100))

Proof:

When n >= 32,

(3n + 13)(7n + 2)(log(1024n² + 100)) <= (3n + 13n)(7n + 2n)(log(1024n² + 1024n²))

(3n + 13)(7n + 2)(log(1024n² + 100)) <= (3n + 13n)(7n + 2n)(log(2(1024n²))

(3n + 13)(7n + 2)(log(1024n² + 100)) <= (16n)(9n)(log2 + log1024n²)

(3n + 13)(7n + 2)(log(1024n² + 100)) <= (144n²)(log2 + 2log32n)

(3n + 13)(7n + 2)(log(1024n² + 100)) <= (144n²)(log32n + 2log32n)

(3n + 13)(7n + 2)(log(11024n² + 100)) <= (144n²)(3log32n)

(3n + 13)(7n + 2)(log(1024n² + 100)) <= 432(n²)(log32n)

(3n + 13)(7n + 2)(log(1024n² + 100)) <= 432(n²)(log32 + logn)

(3n + 13)(7n + 2)(log(11024n² + 100)) <= 432(n²)(logn + logn) ......... {as n >= 32}

(3n + 13)(7n + 2)(log(1024n² + 100)) <= 432(n²)(2logn)

(3n + 13)(7n + 2)(log(1024n² + 100)) <= 864(n²logn)

When n >= 1

(3n)(7n)(logn²) <= (3n + 13)(7n + 2)(log(1024n² + 100))

21n²(logn²) <= (3n + 13)(7n + 2)(log1024n² + 100))

42n²(logn) <= (3n + 13)(7n + 2)(log(1024n² + 100))

Thus from here, we can conclude that,

42(n²logn) <= (3n + 13)(7n + 2)(log(1024n² + 100)) <= 864(n²logn) for all n >= 32

So here g(n) = n²logn and

c₁ = 42 , c₂ = 864 and n₀ = 32

So, from (i):

f(n) = Θ(g(n)

(3n + 13)(7n + 2)(log(1024n² + 100)) = Θ(n2) for all n >= 32