Mathematical Foundation of Computer Science

DHARM

76 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

3.7 Show that the solution of the Fibonacci recurrence i.e., fn = fn–1 + fn–2 for n >1, f 0 = 0 and f 1 = 1

is θ(∅n), where ∅ = ½(1 + 5 ).

3.8 Solve the following recurrences, given T(1) = 1.

(i)T(n) = 3T(n/8) + n^2 2 n logn, n ≥ 8 and n is power of 8.

(ii)T(n) = 27T(n/3) + 11n^3 , n ≥ 3 and n is power of 3.

(iii)T(n) = 128T(n/2) + 2n/n, n ≥ 2 and n is power of 2.

(iv)T(n) = 128T(n/2) + log^3 n, n ≥ 2 and n is power of 2.

3.9 Use Strassen’s algorithm to compute the product^13

57

24

68

F

HG

I

KJ

F

HG

I

KJ

.