Algorithms and Data Structures, Aalborg University (INF1, Autumn'05)

Algorithms and Data Structures (INF1, Autumn'05)

Exercise Set 3

In all exercises assume that n ranges over natural numbers and that all the functions are nonnegative.

Exercise 1:

Exercise 2.1 from Algorithms and Data Structures: Design, Correctness and Analysis by Jeffrey H. Kingston.

Exercise 2 (hand-in):

Solve the following recurrence equation.

T(1) = 7
T(n) = 2 + T(n-1) n>1

Prove that your solution is correct.

Exercise 3:

Solve the following reccurrence equation.

T(0) = 1
T(n) = n.T(n-1) n>1

Prove that your solution is correct.

Exercise 4:

Exercise 2.5 from Algorithms and Data Structures: Design, Correctness and Analysis by Jeffrey H. Kingston.

Solve the reccurrence equation (you may assume that n = 2^k).

Prove that your solution is correct.

Exercise 5:

Exercise 2.11 from Algorithms and Data Structures: Design, Correctness and Analysis by Jeffrey H. Kingston.

Exercise 6:

Prove that

a) n+4 in O(n)
b) 3.n⁵ + 2.n³ is O(n⁵)
c) n⁷ is O(2ⁿ)
d) n².log n = Ω(2.n²)
e) 5.n² + 2.n + 4 = Θ(n²)

Exercise 7:

Give a simplified big-O notation for the following running times:

T(n)=20.n²
T(n)=10.n³ + 6.n
T(n)=2ⁿ + n¹⁶⁹¹
T(n)=1000.n + n²
T(n)= log₅(3.n⁴)

Exercise 8:

It is true that 2ⁿ = Θ(3ⁿ)?

Exercise 9:

Prove that if f(n)=O(g(n)) and g(n)=O(h(n)) then also f(n)=O(h(n)).