# proving big theta [duplicate]

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$$

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

• 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? – Apass.Jack Mar 19 at 10:45
• I have I'm just not sure exactly what is going on with it – Pythonlover Mar 19 at 10:47
• Let $c_1=10$ and $c_2=13$. – Apass.Jack Mar 19 at 11:05
• brilliant thank you! how do you know that? I got 13 I think at some stage – Pythonlover Mar 19 at 11:39
• 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. – rranjik Mar 19 at 16:19

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.

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

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).