This is a homework problem and I'm not sure if I am doing it correctly.

Show that $\log(n^2+1)\in \Theta(\log n)$.

I got:

$$ \log (n^2) \leq \log(n^2+1) \leq \log (n^2+n^2) $$ $$ 2\log n \leq \log(n^2+1) \leq \log(2\cdot n^2) $$ $$ 2\log n \leq \log (n^2+1) \leq \log 2 + \log(n^2)$$ $$ 2\log n \leq \log(n^2+1) \leq 1 + 2\cdot\log n$$

I'm not sure if I have proved it according to the definition that a function $f(x)$ is in $Θ(g(x))$ if there exist positive constants $a,b$, and $n_0$ such that $a\cdot g(x) ≤ f(x) ≤ b\cdot g(x)$ for all $n > n_0$.

I feel like I did something wrong here.

  • 3
    $\begingroup$ This question appears to be unsuited for this site because questions of the form: "Please grade my solution to this exercise problem" are not interesting for anyone but you. Please see this related meta discussion, and these hints on asking questions about exercise problems. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly and it may be reopened. $\endgroup$ – David Richerby Jan 12 '17 at 23:11
  • $\begingroup$ See also our reference question. $\endgroup$ – Raphael Jan 14 '17 at 12:15

In order to prove that $\log(n^2+1) \in \Theta(\log n)$ according to your definition, you have to produce $a,b,n_0$ such that $a \log n \leq \log(n^2+1) \leq b\log n$ for all $n \geq n_0$. This is not what you did. What you have shown is some other inequality.

To help you in future such questions, here is a complete proof. We choose $a = 2$, $b = 3$, and $n_0 = 2$. So we have to show that for $n \geq 2$, $$ 2\log n \leq \log(n^2+1) \leq 3\log n. $$

The first inequality follows from $$ \log(n^2+1) \geq \log(n^2) = 2\log n. $$ You did that part correctly.

The second inequality follows from $$ \log(n^2+1) \leq \log(n^2+n^2) = \log(2n^2) \leq \log(n^3) = 3\log n. $$ This is the part you did incorrectly.


Remember that Θ doesn't care about constant factors, and $log (x^k) = k·log (x)$, so replacing $x$ with $x^k$ doesn't change Θ. Θ also only cares about large n.

If n ≥ 2 then $n^2 + 1 ≤ n^3$, so $log (n^2 + 1) ≤ log (n^3) ≤ 3 log (n)$, therefore $log (n^2 + 1) = Θ (3 log n)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.