I have 6 functions that I have to determine which of 4 given $\Theta$-classes or neither of them.
Example of a function I have been given:
\begin{align*}
\textit{$f_1$}(n) =&(17\textit{n}+1) \\
\end{align*}
The $\Theta$-classes I have been given:
\begin{align*}
\Theta&(1), \\
\Theta&(\log\textit{n}), \\
\Theta&(\textit{$n^a$}), \\
\Theta&(\textit{$a^n$}), \\
or& none
\end{align*}
How do I go about this subject and determine the classes?
So far I believe that $f_1$(n) has $\Theta(\textit{$n^a$})$,
But I'm not entirely sure.
Best Answer
A function $f$ is $f = \Theta(g)$, that is bounded below and above by $g$ asymptotically, if $k_1,k_2,n_0 \in \mathbb Z_{\ge0}$ exist, such that $$k_1 g(n) \le f(n) \le k_2 g(n) \forall n \ge n_0.$$
For your first two functions you get the following result:
\begin{align*} n \le &(17n+1) &\le 18 n &\text{ for } n \ge 1 &\text{ therefore }f_1(n) = \Theta(n^1)\\ n^2 \le &(n^2+10n+1) &\le 20 n^2 &\text{ for } n \ge 1 &\text{ therefore }f_2(n) = \Theta(n^2)\\ \end{align*}
Now for $f_3$ notice that $n^{1000}$ has a large exponent, but the term $1.001^n$ will dominate it around $n_0 = 1.664 \cdot 10^7$. So overall we have
\begin{align*} 1.001^n \le n^{1000} + 1.001^n + 1000 \le 3 \cdot 1.001^n& \text{ for } n \ge 10^8 &\text{ therefore }f_3(n) = \Theta(1.001^n) \end{align*}
Note that the constants $k_1$ and $k_2$ don't need to be sharp for the actual analysis, as long as the inequalities hold.
Now you should be able to answer the other functions' complexity classes.