- #1

- 782

- 1

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

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

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

Last edited: