1

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.

cenh
  • 35
  • Asymptotic expressions should trigger similar parts of your knowledge as $\lim_{n \to +\infty}$ does. In this case, that $1$ is insignificant compared to $17n$, and so the $+1$ can probably be eliminated. –  Oct 07 '13 at 20:54

1 Answers1

0

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.

Zeta
  • 133
  • Please, replace every θ by \Theta. – Did Oct 05 '13 at 15:47
  • Hmm, so both $f_1$ and $f_2$ = $\Theta(\textit{$n^a$})$ and $f_3$ = $\Theta(a^n)$ ? – cenh Oct 05 '13 at 15:48
  • @Did: Sorry, I didn't think MathJax would support \Theta. – Zeta Oct 05 '13 at 15:50
  • @Cralle: Indeed. However, note that $a$ is actually part of the class, e.g. $n^2 \neq \Theta(n^3)$, $2^n \neq \Theta(3^n)$. So if you want to compare two functions from $\Theta(n^a)$ you need the actual constant. – Zeta Oct 05 '13 at 15:57
  • @Zeta: Okay, I think I understand it better now. Is there any of the functions that doesn't belong to one of the 4 $\Theta$-classes? – cenh Oct 05 '13 at 16:09
  • @Cralle: No. All functions are in one of the classes, which is expected for such functions. An example for a time-complexity which isn't in those classes is Bubblesort, where you stop as soon as you note that your list is sorted. It has a best-case-complexity of $O(n)$, and a worst-case complexity of $O(n^2)$, thereby it is neither $\Theta(n)$ nor $\Theta(n^2)$. – Zeta Oct 05 '13 at 16:25
  • @Zeta: Ah, okay. I guess it was more of a trick when, I was given the option "none of the above". – cenh Oct 05 '13 at 17:33
  • @Cralle: As long as the opening parentheses in $f_3$ is wrong, yes. – Zeta Oct 05 '13 at 18:56
  • @Zeta: Yes that was an mistake (Made the same one in $f_6$ appaerently). Anyways made the rest of the assignment and $f_4$, $f_5$ and $f_6$ all gives log(n) if I did everything correctly. Is this correct? – cenh Oct 05 '13 at 19:15
  • @Cralle: No, since $log(n)$ is dominated by $n^a$. Even though the exponent might be small, linear (or polynomial) growth trumps logarithmic. However, note that comments are not meant for long discussions. Since you do not have enough reputation for chat, it might be a good idea to post follow-up questions as new questions. – Zeta Oct 05 '13 at 19:18