2 It's n^α not nα, which leads to n * f(n) = n * (n^α) = n^(α + 1)
source | link

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
source | link

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)