Skip to main content
Computer Science

Return to Answer

Clarified phrasing
Source Link
David Richerby
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

The questionexercise being asked about is pretty stupid (this is criticism against its poserthe person who set it as an exercise, not the OP). Every (positive) function $f$ is its own big $\Theta$, that is $f(n) = \Theta(f(n))$. Nevertheless, whoever asked the question expected the following answers: $f(n) = \Theta(n^3)$ and $f(n) = \Theta(\log n)$. There are many online and offline resources that can explain why this is the case and how to prove it, or you can try working through the algebra yourself.

Please let the poser know that the following answers are as mathematically correct as the expected one: $n^3 - 3n^2 + 5 = \Theta(17n^3 - 2n\log n + 4\log\log n)$ and $2\log_2 n - 4 = \Theta(4\log_4 n - 2)$. In order to rule out these answers, the poser should have phrased the question as follows:

For each of the following functions $f(n)$, find a function $g(n)$ of the form $n^\alpha (\log n)^\beta$ such that $f(n) = \Theta(g(n))$, and prove that $f(n) = \Theta(g(n))$.

Note that in general thea function $g(n)$ of that specific form might not exist, for example if $f(n) = n\log\log n$, or for the following more exotic function: $$f(n) = \begin{cases} n & \text{ if $n$ is odd,} \\ n^2 & \text{ if $n$ is even.} \end{cases}$$ Such functions nearly show up in modular exponentiation, FFT-based algorithms, and fast matrix multiplication, though in these cases the difference is only in the constant (e.g. $n$ vs. $2n$) rather than the asymptotics.

The question is pretty stupid (this is criticism against its poser, not the OP). Every (positive) function $f$ is its own big $\Theta$, that is $f(n) = \Theta(f(n))$. Nevertheless, whoever asked the question expected the following answers: $f(n) = \Theta(n^3)$ and $f(n) = \Theta(\log n)$. There are many online and offline resources that can explain why this is the case and how to prove it, or you can try working through the algebra yourself.

Please let the poser know that the following answers are as mathematically correct as the expected one: $n^3 - 3n^2 + 5 = \Theta(17n^3 - 2n\log n + 4\log\log n)$ and $2\log_2 n - 4 = \Theta(4\log_4 n - 2)$. In order to rule out these answers, the poser should have phrased the question as follows:

For each of the following functions $f(n)$, find a function $g(n)$ of the form $n^\alpha (\log n)^\beta$ such that $f(n) = \Theta(g(n))$, and prove that $f(n) = \Theta(g(n))$.

Note that in general the function $g(n)$ might not exist, for example if $f(n) = n\log\log n$, or for the following more exotic function: $$f(n) = \begin{cases} n & \text{ if $n$ is odd,} \\ n^2 & \text{ if $n$ is even.} \end{cases}$$ Such functions nearly show up in modular exponentiation, FFT-based algorithms, and fast matrix multiplication, though in these cases the difference is only in the constant (e.g. $n$ vs. $2n$) rather than the asymptotics.

The exercise being asked about is pretty stupid (this is criticism against the person who set it as an exercise, not the OP). Every (positive) function $f$ is its own big $\Theta$, that is $f(n) = \Theta(f(n))$. Nevertheless, whoever asked the question expected the following answers: $f(n) = \Theta(n^3)$ and $f(n) = \Theta(\log n)$. There are many online and offline resources that can explain why this is the case and how to prove it, or you can try working through the algebra yourself.

Please let the poser know that the following answers are as mathematically correct as the expected one: $n^3 - 3n^2 + 5 = \Theta(17n^3 - 2n\log n + 4\log\log n)$ and $2\log_2 n - 4 = \Theta(4\log_4 n - 2)$. In order to rule out these answers, the poser should have phrased the question as follows:

For each of the following functions $f(n)$, find a function $g(n)$ of the form $n^\alpha (\log n)^\beta$ such that $f(n) = \Theta(g(n))$, and prove that $f(n) = \Theta(g(n))$.

Note that in general a function $g(n)$ of that specific form might not exist, for example if $f(n) = n\log\log n$, or for the following more exotic function: $$f(n) = \begin{cases} n & \text{ if $n$ is odd,} \\ n^2 & \text{ if $n$ is even.} \end{cases}$$ Such functions nearly show up in modular exponentiation, FFT-based algorithms, and fast matrix multiplication, though in these cases the difference is only in the constant (e.g. $n$ vs. $2n$) rather than the asymptotics.

Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

The question is pretty stupid (this is criticism against its poser, not the OP). Every (positive) function $f$ is its own big $\Theta$, that is $f(n) = \Theta(f(n))$. Nevertheless, whoever asked the question expected the following answers: $f(n) = \Theta(n^3)$ and $f(n) = \Theta(\log n)$. There are many online and offline resources that can explain why this is the case and how to prove it, or you can try working through the algebra yourself.

Please let the poser know that the following answers are as mathematically correct as the expected one: $n^3 - 3n^2 + 5 = \Theta(17n^3 - 2n\log n + 4\log\log n)$ and $2\log_2 n - 4 = \Theta(4\log_4 n - 2)$. In order to rule out these answers, the poser should have phrased the question as follows:

For each of the following functions $f(n)$, find a function $g(n)$ of the form $n^\alpha (\log n)^\beta$ such that $f(n) = \Theta(g(n))$, and prove that $f(n) = \Theta(g(n))$.

Note that in general the function $g(n)$ might not exist, for example if $f(n) = n\log\log n$, or for the following more exotic function: $$f(n) = \begin{cases} n & \text{ if $n$ is odd,} \\ n^2 & \text{ if $n$ is even.} \end{cases}$$ Such functions nearly show up in modular exponentiation, FFT-based algorithms, and fast matrix multiplication, though in these cases the difference is only in the constant (e.g. $n$ vs. $2n$) rather than the asymptotics.