Asymptotisk notation: Funktioner og Summer

Spørgsmål 1

I det følgende angiver $\log n$ 2-tals-logaritmen af $n$.

	ja	nej
$n^{1/2}$ er $O(\sqrt{n})$
$n^{1/2}$ er $\Omega(\sqrt{n})$
$n^2\cdot(\log n)^2$ er $O(n^3)$
$7n\log n$ er $\Omega(n)$
$n^2$ er $O(\frac{1}{2}n^4)$
$\sqrt{n}$ er $O(\log^7 n)$
$2^n$ er $O(n^4)$
$n\log n$ er $O(n^{3/2})$
$\log n$ er $O(\sqrt{n})$
$8\cdot 2^n$ er $O(n^3)$
$n^2$ er $O(n^3/\log n)$
$n^7$ er $O(2^{8\log n})$
$n^7$ er $O(2^{4\log n})$
$3n^2$ er $O(n+n^3)$
$8\cdot 2^n$ er $O(4^n)$
$7\log n$ er $O(n^{1/7})$
$7n^7+7n$ er $O(14n)$

Spørgsmål 2 - Sums of Series

	$\Theta(n)$	$\Theta(n \log n)$	$\Theta(n^2)$
$\sum_{i=1}^n i = 1 + 2 + 3 + \cdots + n$
$\sum_{i=0}^{\log n} 2^i = 1 + 2 + 4 + 8 + \cdots + n$
$\sum_{i=1}^{n} \log i = \log 1 + \log 2 + \log 3 + \log 4 + \cdots + \log n$
$\sum_{i=0}^{\log n} \frac{n}{2^i} = n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \cdots + \frac{n}{n}$

Spørgsmål 3

In the following $f$ and $g$ are unknown functions. Assume that $f(n) = O(g(n))$.

	ja	nej
$f(n) \leq g(n)$
$f(n) = \Theta( g(n) )$
$g(n) = O(f(n))$
$g(n) = \Omega(f(n))$
$f(n) = O(2^{g(n)})$
$f(n) = O(\log g(n))$
$f(n) = O(g(n) - f(n))$
$f(n) = O(g(n) + f(n))$

0% besvaret