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