# Return to Answer

 2 It's n^α not nα, which leads to n * f(n) = n * (n^α) = n^(α + 1) edit approved Jul 10 '15 at 18:21 Shoe 30911 gold badge22 silver badges1515 bronze badges Recurrence equation: `````` | e if n = 1 T(n) = | | T(n - 1) + d if n > 1 f(n) = d so is a 0-degree polynomial, n^0 T(n) ∈ Θ(n^0+1) = Θ(n) `````` Method for Chip & Conquer The problem of size n is chipped down into one subproblem of size n-c. ``````The problem of size n is chipped down into one subproblem of size n-c. T(n) = T(n - c) + f(n) If c > 0 (the chipping factor)   f(n) - nonrecursive cost (to create subproblem and/or combine with solutions of other subproblems) then T(n) can be asymptotically bounded as follows: If f(n) is a polynomial nα, then T(n) ∈ Θ(n^α+1) If f(n) is lg n, then T(n) ∈ Θ(n lg n) `````` If `c > 0` (the chipping factor) and f(n) is the nonrecursive cost (to create subproblem and/or combine with solutions of other subproblems) then T(n) can be asymptotically bounded as follows: If f(n) is a polynomial `n^α`, then `T(n) ∈ Θ(n^(α+1))` If f(n) is `lg n`, then `T(n) ∈ Θ(n lg n)` Recurrence equation: `````` | e if n = 1 T(n) = | | T(n - 1) + d if n > 1 f(n) = d so is a 0-degree polynomial, n^0 T(n) ∈ Θ(n^0+1) = Θ(n) `````` Method for Chip & Conquer ``````The problem of size n is chipped down into one subproblem of size n-c. T(n) = T(n - c) + f(n) If c > 0 (the chipping factor)   f(n) - nonrecursive cost (to create subproblem and/or combine with solutions of other subproblems) then T(n) can be asymptotically bounded as follows: If f(n) is a polynomial nα, then T(n) ∈ Θ(n^α+1) If f(n) is lg n, then T(n) ∈ Θ(n lg n) `````` Recurrence equation: `````` | e if n = 1 T(n) = | | T(n - 1) + d if n > 1 f(n) = d so is a 0-degree polynomial, n^0 T(n) ∈ Θ(n^0+1) = Θ(n) `````` Method for Chip & Conquer The problem of size n is chipped down into one subproblem of size n-c. ``````T(n) = T(n - c) + f(n) `````` If `c > 0` (the chipping factor) and f(n) is the nonrecursive cost (to create subproblem and/or combine with solutions of other subproblems) then T(n) can be asymptotically bounded as follows: If f(n) is a polynomial `n^α`, then `T(n) ∈ Θ(n^(α+1))` If f(n) is `lg n`, then `T(n) ∈ Θ(n lg n)` 1 answered Mar 14 '13 at 7:56 Nishant 11122 bronze badges Recurrence equation: `````` | e if n = 1 T(n) = | | T(n - 1) + d if n > 1 f(n) = d so is a 0-degree polynomial, n^0 T(n) ∈ Θ(n^0+1) = Θ(n) `````` Method for Chip & Conquer ``````The problem of size n is chipped down into one subproblem of size n-c. T(n) = T(n - c) + f(n) If c > 0 (the chipping factor) f(n) - nonrecursive cost (to create subproblem and/or combine with solutions of other subproblems) then T(n) can be asymptotically bounded as follows: If f(n) is a polynomial nα, then T(n) ∈ Θ(n^α+1) If f(n) is lg n, then T(n) ∈ Θ(n lg n) ``````