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

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 n0 and c1 and c2 such that, to the right of n0 the f(n) always lies between c1g(n) and c2g(n) inclusive.

Θ(g(n)) = {f(n) : There exist positive constant c1, c2 and n0 such that 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n), for all n ≥ n0

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)$