AU logo

Algoritmer og Datastrukturer

Multiple-choice opgaver

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