0
$\begingroup$

This question already has an answer here:

How would I tackle this equation? $$10n^3 +3n = \Theta(n^3)$$

I know I have to solve Big $O$ and Big $\Omega$ but have no idea how to do this. I got as far as

$$10n^3+3n \leq c_1n^3$$

$$0 \leq c_1n^3 \leq 10n^3+3n \leq c_2n^3$$

$\endgroup$

marked as duplicate by David Richerby, Apass.Jack, Evil, Draconis, Yuval Filmus Mar 20 at 18:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Have you tried following the definition of big $\Theta$? Please edit the question to show your partial progress and where you got stuck. For example, if you did not understand what is big $\Theta$, tell us where you did not understand it. You could also show whether you had understood at least one particular example about $\Theta$. If not, where did you not understand? $\endgroup$ – Apass.Jack Mar 19 at 10:45
  • $\begingroup$ I have I'm just not sure exactly what is going on with it $\endgroup$ – Pythonlover Mar 19 at 10:47
  • 2
    $\begingroup$ Let $c_1=10$ and $c_2=13$. $\endgroup$ – Apass.Jack Mar 19 at 11:05
  • $\begingroup$ brilliant thank you! how do you know that? I got 13 I think at some stage $\endgroup$ – Pythonlover Mar 19 at 11:39
  • 1
    $\begingroup$ Please check this one: cs.stackexchange.com/a/105535/59189. The steps are the same, and as Apass.Jack mentioned, you will get used to it so quickly that you will not be doing it on paper more than a couple of times. $\endgroup$ – rranjik Mar 19 at 16:19
2
$\begingroup$

You may find the limit definitions much more simpler. So let $f(n) = 10n^3 + 3n$. You want to prove that

(i) $f(n) = \lim_{n \to \infty} f(n) / n^3 < \infty$, and that

(ii) $f(n) = \lim_{n \to \infty} f(n) / n^3 > 0$.

Now you only need to apply elementary algebra.

$\endgroup$
  • $\begingroup$ +1. From personal experience, some students find the limit definition much easier to work with. (It depends on one's math background, I suppose.) $\endgroup$ – dkaeae Mar 19 at 14:38
  • $\begingroup$ Nitpicking, it should be called elementary calculus instead of elementary algebra. $\endgroup$ – Apass.Jack Mar 19 at 14:52
0
$\begingroup$

The definition of $f(n) = O(g(n))$ (for $n \to \infty$) is that there are $N_0, c$ such that for $N \geq N_0$ it is $f(n) \leq c g(n)$.

In your case, pick e.g. $N_0 = 2$, then you have $10 n^3 + 3 n < 10 n^3 + 3 n^3 = 13 n^3$, and $c = 13$ works.

The definition of $f(n) = \Omega(g(n))$ (for $n \to \infty$) is that there are $N_0, c$ such that for $N \geq N_0$ it is $f(n) \geq c g(n)$.

Pick e.g. $N_0 = 5$, so $10 n^3 + 3 n > 10 n^3$, and $c = 10$ works.

Now, $f(n) = \Theta(g(n))$ if both $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$, and you are done.

Note the $N_0$, $c$ don't have to be the same (usually at least $c$ is different).

$\endgroup$

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