Question

1. Find the theta notation of the following:

a. 6n ³+ 12n ² + 1, for nà ƒ ƒ ¢ ‰ ¥1

b. 3n ²+ 2n log2 n, for nà ƒ ƒ ¢ ‰ ¥1

2. Find the theta notation for the number of times the statement x:=x + 1 is executed.

a. for i:=1 to 2n do x=x+1

b. for i;=1 to 2n do for i;=1 to n do X:=x +1

Answer 1

1.

Big-Theta(Θ) notation gives bound for a function f(n) to within a constant factor.

We write f(n) = Θ(g(n)), If there are positive constants n₀ and c₁ and c₂ such that, to the right of n₀ the f(n) always lies between c₁g(n) and c₂g(n) inclusive.

Θ(g(n)) = {f(n) : There exist positive constant c₁, c₂ and n₀ such that 0 ≤ c₁ g(n) ≤ f(n) ≤ c₂ g(n), for all n ≥ n₀

a.

$c_1n^3\le$ 6n ³+ 12n ² + 1$\le c_2n^3$

$f(n)=\theta(n^3)$

b.

$c_1n^2\le$ 3n ²+ 2n log2 n$\le c_2n^2$

$f(n)=\theta(n^2)$

2.

a.

$f(n)=2n$

$c_1n\le 2n\le c_2n$

$f(n)=\theta(n)$

b.

$f(n)=2n^2$

$c_1n^2\le 2n^2\le c_2n^2$

$f(n)=\theta(n^2)$