# Big-O and recurrence equations.

• cscott
After reviewing the conversation, in summary, the participants discussed the topic of recurrence equations and their proofs using mathematical induction. They also mentioned the use of big-O notation in measuring the efficiency of algorithms and provided an example of proving 30000n^2 is O(n^3). However, there was some confusion about the complexity class of 30000n^2, with some saying it is O(n^2) and others saying it is O(n^3 \log n). The conversation also mentioned the concept of the Master theorem and how it relates to recurrence relations.

#### cscott

Can anyone point me to resources showing me how to prove recurance equations like:

$I(n) \le c$ if n = 0
$d+I(n-1)$ if n >= 1

i.e. $$I(n) \le c + dn$$

Also for proving things like: $30000n^2 + n \log n$ is $O(n^3)$ using the basic definition of big-O notation ($f(n) \le k \cdot g(n)$ for some k and $n \le n_0$)

I never took algebra so I never learned this stuff while CS majors did :( It'd be helpful if I knew what to search for.

Last edited:
Hi,

I'm not sure I entirely understand your example but generally recurrence relations can be proven using mathematical induction. Studying proof by mathematical induction will help. The same of method of proof that allows us to prove things like:

$$\sum_{i=1}^{n} i = \frac {n(n + 1)} {2}$$

Also allows us to prove recurrence relations (that is one). There are some variations but at the risk of oversimplifying, the general idea is to establish the truth of a proposition by showing that it follows from smaller instances of the same proposition, as long as the truth of the smallest instance can be explicitly established. Proofs by induction normally involve establishing the truth of a base case and then the application of an inductive hypothesis (inductive step) which we assume to be true to show the truth of the proposition, no matter what size, follows from the truth of all the previous propositions.

Regarding big-O, the whole purpose for it's existence is to provide a "fuzzy ruler" with which to measure the efficiency of algorithms. With that in mind, we normally want leave out tricky things like constants and such. For easy examples like the one you listed it is sufficient to note that:

$30000n^2 + n \log n \epsilon O(n^3)$

By noting that:

$30000n^2 + n \log n < n^2 + n^2 = 2n^2 < 2n^3$

Thus, $30000n^2 + n \log n \epsilon O(n^3)$ for very large n.

For harder functions it helps to study the asymptotic behavior of the functions in question. That is to say, to see if $f(n) \epsilon O(g)$ we look at the limit:

$\lim_{n\rightarrow\infty}\frac {f(n)} {g(n)}$

From there we have a couple possibilities. If the limit exists and is finite we know that $f(n) \epsilon O(g)$. If the limit is infinity then $f(n) \neg\epsilon O(g)$. Additionally if the limit is finite and non zero we can say that $O(f) = O(g)$

Last edited:
$30000n^2 + n \log n$ is $O(n^3)$.

Are you guys sure about that? I could have sworn it was $$O(n^2)$$

I've used induction to prove convergence in sequences or formulas like you posted but I've never used it in the context of CS.

So parabrham you are saying basically $n log n \le n^2$, adding the two $n^2$'s (drop 30000) and saying theyre less than $x^3$?? I thought we always went with the best possible order...

I would have said O(n^2) as well but they also say prove $30000n^2$ is $O(n^3 \log n)$?!? I don't understand how $30000n^2$ isn't simply $O(n^2)$.

Last edited:
Alkatran said:

Yes that's discussing recurrence relations. But the $30000n^2 + n \log n$ was not given as part of a recurrence relation but just a simple function of n.

$$30000n^2 + n \log n < 30001 n^2$$ and is therefore $$O(n^2)$$

Last edited:
cscott said:
I've used induction to prove convergence in sequences or formulas like you posted but I've never used it in the context of CS.

So parabrham you are saying basically $n log n \le n^2$, adding the two $n^2$'s (drop 30000) and saying theyre less than $x^3$?? I thought we always went with the best possible order...

I would have said O(n^2) as well but they also say prove $30000n^2$ is $O(n^3 \log n)$?!? I don't understand how $30000n^2$ isn't simply $O(n^2)$.

You guys are correct. Sorry I was away for a bit.