-2
$\begingroup$

How would I prove that the statement

$10n^3+3n=Θ(n^3)$

is true/false?

$\endgroup$
4
  • 3
    $\begingroup$ There is no "equation" here. Either the function $n \mapsto 10n^3 + 3n$ is in $\Theta(n^3)$ or not. Review the appropriate definitions. $\endgroup$
    – dkaeae
    Mar 13, 2019 at 14:38
  • $\begingroup$ You should start by looking at the relevant definitions. $\endgroup$
    – Juho
    Mar 13, 2019 at 16:45
  • $\begingroup$ Have this in mind: $10n^3+3n=Θ(n^3)$ is an abuse of notation. This is what they intend to say: $10n^3+3n$ belongs to $Θ(n^3)$. $\endgroup$
    – rranjik
    Mar 13, 2019 at 17:13
  • $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$
    – Raphael
    Mar 13, 2019 at 19:59

2 Answers 2

2
$\begingroup$

Remember that, $10n^3+3n=Θ(n^3)$ is an abuse of notation. Think of $Θ(n^3)$ as a set/class of functions. You are prove to that $10n^3+3n$ belongs to that set.

Simply put, every element in the set has a property, and everything that has the property belongs to the set ("if and only if" is the mathy way they say this). A function $f(n)$ belongs to $Θ(g(n))$ if that property holds.

So, what is that property exactly ?

$C_1g(n) ≤ f(n) ≤ C_2 g(n)$ whenever $n > k$

Well, what does that mean ? For a decently large $n$, every element (called $f(n)$ here) in the set (which is $Θ(g(n))$ here), is smaller than a constant ($C_2$) times $g(n)$, and also it is always larger than a different constant ($C_1$) times $g(n)$.

Note that that the inequality implies, $\frac{f(n)}{g(n)} ≤ C_2$ and $C_1 ≤ \frac{f(n)}{g(n)}$. All we have left to do is to find such a $C_1$ and $C_2$.

Consider

$\frac{10n^3+3n}{n^3}$

this is always less than or equal to $\frac{10n^3+3n^3}{n^3}$ - because we assume $n$ is a positive integer and so $n^3$ is always at least $n$ - which is less than or equal to $13$. This proves the $\frac{f(n)}{g(n)} ≤ C_2$ part.

Moreover $\frac{10n^3+3n}{n^3}$ is greater than or equal to $\frac{10n^3}{n^3}$. Again as n is positive dropping $3n$ could only make it smaller. This implies the constant $C_1$ is $10$, the second part.

The first part proves that $f(n)$ belongs to $O(g(n))$ and the second proves $\Omega(g(n))$ which implies $Θ(g(n))$ usually.

So this gives a sloppy bound that this function could only be 13 times as big, and 10 times as small. $10n^3 ≤ 10n^3 + 3n ≤ 13n^3$. To be precise we assumed $n>1$ and $k=1$ here. Use the limit definition for an exact proof. But this is pragmatic and should be enough in most cases.

$\endgroup$
4
  • $\begingroup$ Surely that's $O$, not $\Theta$? $\endgroup$
    – Draconis
    Mar 13, 2019 at 18:14
  • $\begingroup$ Oopsies! Sorry for the wrong answer. I thought it was big O. Let me delete it now. $\endgroup$
    – rranjik
    Mar 13, 2019 at 18:14
  • $\begingroup$ @Draconis thank you very much for pointing out. I did not want to delete the answer. I have edited this to prove $\Theta$. I totally thought it was $O$ when I wrote this the first time. Please check this if you get a chance. $\endgroup$
    – rranjik
    Mar 13, 2019 at 18:57
  • 1
    $\begingroup$ All seems correct; I'd use some different notation but that's just a matter of convention. $\endgroup$
    – Draconis
    Mar 13, 2019 at 19:23
1
$\begingroup$

This isn't really an equation. The equals sign in the middle is an abuse of notation: $\Theta(n^3)$ is a set of functions, not a single function, so it should more properly be written $(10n^3+n) \in \Theta(n^3)$.

The formal definition of $\Theta(n^3)$ is something like this:

$\Theta(n^3)$ is the set of all functions $f(n)$ such that, for some specific choice of constants $N, C, D$, then $n > N \implies Cn^3 < f(n) < Dn^3$.

Basically, when $n$ gets really big, $\Theta(n^3)$ means that the function starts to "look like" $n^3$, up to a constant factor. There's a useful lemma here which helps more:

For a function $f(n)$, if $\lim_{n \rightarrow \infty} \frac{f(n)}{n^3}$ exists and is a positive constant, then $f(n) \in \Theta(n^3)$.

This is much easier to use here, in my opinion. With a bit of algebra, we can say that $\lim_{n \rightarrow \infty} \frac{10n^3+n}{n^3} = \lim_{n \rightarrow \infty} \frac{10n^3}{n^3} + \lim_{n \rightarrow \infty} \frac{n}{n^3} = 10+0 = 10$. Since ten is a positive constant, we've shown that $(10n^3+n) \in \Theta(n^3)$.

$\endgroup$
0

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