CMPE/CISC 365 - Lab 1

Is $\log^k n \in {\cal O}(n)$ for any $k \geq 1$ ?

Is $n^{0.001} \in {\cal O}( \log n )$ ?

Is $n^k \in {\cal O}(2^n)$ for any $k \geq 1$ ?

• yes
• no

Suppose all algorithms that solve a particular problem are in $\Omega( n^3 )$.

Using the above fact, what is the strongest statement (of those below) that can be made about the fastest algorithm that solves this problem in time $f(n)$?

• $f(n) \in {\cal O}( n^3 )$
• $f(n) \in \Theta( n^3 )$
• $f(n) \in \Omega( n^3 )$

What is the asymptotic complexity of

$\displaystyle T(n) = \left\{ \begin{array}{ll} c & \textrm{ if } n < 1 \\ f(n) + T(n-1) & \textrm{ otherwise} \\ \end{array} \right.$

• ${\cal O}(n)$
• ${\cal O}(f(n))$
• ${\cal O}(n \; f(n))$

What is the asymptotic complexity of

$\displaystyle T(n) = \left\{ \begin{array}{lcl} c && \textrm{if } n \leq 1 \\ n + a \; T( {n \over b} ) && \textrm{otherwise} \\ \end{array} \right.$

when a,b = 2,4?

when a,b = 3,3?

when a,b = 4,2?

• ${\cal O}(n)$
• ${\cal O}(n \log n)$
• ${\cal O}(n^2)$
• ${\cal O}(n^2 \log n)$
• ${\cal O}(n^3)$

What is the tightest aymptotic complexity (from the list below) of

$\displaystyle T(n) = \left\{ \begin{array}{lcl} c && \textrm{if } n \leq 2 \\ T(n-1) + T(n-2) && \textrm{otherwise} \\ \end{array} \right.$

• ${\cal O}(n^2)$
• ${\cal O}(n^3)$
• ${\cal O}(2^n)$
• ${\cal O}(3^n)$