Example(continued) We must also handle the initial conditions that is, ground the induction with base cases Base: I(n)=o(1) for all n<no, where no is a suitable constant For1≤n<mo, we have((1)≤cn3,ifwe pick c big enough This bound is not tight. Day 3 Introduction to Algorithms 2.5Day 3 Introduction to Algorithms L2.5 Example (continued) • We must also handle the initial conditions, that is, ground the induction with base cases. • Base: T(n) = Θ(1) for all n < n0, where n0 is a suitable constant. • For 1 ≤ n < n0, we have “Θ(1)” ≤ cn3, if we pick c big enough. This bound is not tight!