Recurrences

Spørgsmål 1

Solve the following recurrences. Assume that $T(n) = 1$ when $n \leq 2$.

	$O(n)$	$O(n^2)$	$O(n^3)$	$O(n^2 \log n)$	$O(n^2 \sqrt{n})$	$O(\sqrt{n})$	$O(\sqrt{n} \log n)$
$T(n) = 2 T(n/2) + n^2$
$T(n) = T(9n/10) + n$
$T(n) =16 T(n/4) + n^2$
$T(n) = 7 T(n/3) + n^2$
$T(n) = 8 T(n/2) + n^2$
$T(n) = 2 T(n/4) + \sqrt{n}$
$T(n) = T(n/4) + \sqrt{n}$
$T(n) = T(n-1) + n $
$T(n) = 3 T(n/9) + \sqrt{n}$
$T(n) = 4 T(n/2) + n^2\sqrt{n}$

0% besvaret