Can anyone point me to resources showing me how to prove recurance equations like:(adsbygoogle = window.adsbygoogle || []).push({});

[itex]I(n) \le c[/itex] if n = 0

[itex]d+I(n-1)[/itex] if n >= 1

i.e. [tex]I(n) \le c + dn[/tex]

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

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Big-O and recurrence equations.

**Physics Forums | Science Articles, Homework Help, Discussion**