Explore BrainMass
Share

Explore BrainMass

    Big O Problem

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Show that if:

    T(1) = a
    T(n) = T(n-1) + n^k, for n > 1

    then T(n) is O(n^(k+1)). You may assume k>=0. Also, show that this is the tightest simple big-oh upper bound, that is, that T(n) is not O(n^m) if m < k+1. Hint: Expand T(n) in terms of T(n-i), for i = 1,2,..., to get the upper bound. For the lower bound, show that T(n) is at least cn^(k+1) for some particular c >0.

    © BrainMass Inc. brainmass.com October 9, 2019, 4:14 pm ad1c9bdddf
    https://brainmass.com/computer-science/c/big-o-problem-26182

    Solution Summary

    Big O Problem is solved.

    $2.19