Search for question
Question

Q2

You want to show that the solution of T(n) = T(n − 1) +n is O(n²), using

the substitution method. If you plug in recursively, any large C' value will work

within the standard inductive proof, but very small C' values will not work.

The largest C' value that fails within the proof is

If you use C = .75, the smallest no value that you can use that will make the

inductive equation work is

(Note, it is not an integer.)

In both cases, writing the value as a decimal number is probably your best bet,

formatting-wise.

Fig: 1