Description

Data Structures
HW1
Sina Rostami
9822143
Problem 1
Show that 3n2 + 25 is O(n2) :
There must exist n0 and c such that :
3n2 + 25 ≤ c.n2
n ≥ n0
So with c = 4 :
3n2 + 25 ≤ 4n2
25 ≤ n2
5 ≤ n
→ c = 4,n0 = 5
Problem 2
if 4n3 + 7n2 + 12 is O(n3) find its corresponding n0 and k according to the Big O notation formula. :
There must exist n0 and c such that :
4n3 + 7n2 + 12 ≤ k.n3 n ≥ n0
So with k = 4 + 7 + 12 = 23 :
4n3 + 7n2 + 12 ≤ 23n3
19n3− 7n2− 12 ≥ 0
(n − 1)(19n2 + 12n + 12) ≥ 0
(19n2 + 12n + 12) always ≥ 0 → (n − 1) ≥ 0 n ≥ 1
→ k = 23,n0 = 1
Problem 3
Show that nlog(n) − 2n + 13 is Ω(nlog(n)). :
There must exist n0 and c such that :
nlog(n) − 2n + 13 ≥ cnlog(n) n ≥ n0
So with c = 0.1 :

Problem 4
Show that P(n) = n2 + 5n + 7 is Θ(n2). :
Big O :
There must exist n0 and c such that :
n2 + 5n + 7 ≤ cn2 n ≥ n0
So with c = 2 + 5 + 7 = 13 :
n2 + 5n + 7 ≤ 13n2
12n2− 5n − 7 ≥ 0
(n − 1)(12n + 7) ≥ 0 n ≥ 1
→ c = 13,n0 = 1
⇒P(n) ∈O(n2)
Big Ω :
There must exist n0 and c such that :
n2 + 5n + 7 ≥ cn2 n ≥ n0
So with c = 1 and n0 = 0 the unequality is obviously satisfied.
⇒P(n) ∈ Ω(n2)
⇒ P(n) ∈ Θ(n2)
Problem 5
Show that P(n) = 0.5n2− 3n is Θ(n2). :
Big O :
There must exist n0 and c such that :
0.5n2− 3n ≤ cn2 n ≥ n0
So with c = 0.5 :
0.5n2− 3n ≤ 0.5n2 3n ≥ 0 n ≥ 0
→ c = 0.5,n0 = 0
⇒P(n) ∈O(n2)
Big Ω :
There must exist n0 and c such that :
0.5n2− 3n ≥ cn2 n ≥ n0
So with c = 0.4 :
0.5n2− 3n ≥ 0.4n2 0.1n2− 3n ≥ 0 n(0.1n − 3) ≥ 0 n ≥ 30
→ c = 0.4,n0 = 30 ⇒P(n) ∈ Ω(n2)
⇒ P(n) ∈ Θ(n2)
Problem 6
Show that P(n) = 3n2 + 8nlog(n) is Θ(n2). :
Big O :
There must exist n0 and c such that :
3n2 + 8nlog(n) ≤ cn2 n ≥ n0
So with c = 3 + 8 = 11 :
3n2 + 8nlog(n) ≤ 11n2
8n2− 8nlog(n) ≥ 0 n2− nlog(n) ≥ 0
n(n − log(n)) ≥ 0
(n − log(n)) is always > 0 → n ≥ 0 log(0) is undefined → n > 0
→ c = 11,n0 = 1
⇒P(n) ∈O(n2)
Big Ω :
There must exist n0 and c such that :
3n2 + 8nlog(n) ≥ cn2 n ≥ n0
So with c = 1,n0 = 1 the unequality is obviously satisfied.
⇒P(n) ∈ Ω(n2)
⇒ P(n) ∈ Θ(n2)