Explore BrainMass

Explore BrainMass

    Big O problem

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

    Consider the recurrence

    T(1)=a
    T(n)=cT(n/d)+bn^k, for n a power of d

    Iteratively expand T(n) in terms of T(n/d^i) for i=1,2,.... Show that

    a) if c > d^k, then T(n) is O(n^logd c)
    b) if c = d^k, then T(n) is O(n^k log n)
    c) if c < d^k, then T(n) is O(n^k)

    © BrainMass Inc. brainmass.com February 24, 2021, 2:31 pm ad1c9bdddf
    https://brainmass.com/computer-science/algorithms/big-o-problem-26321

    Solution Summary

    This solution helps with a software development problem.

    $2.19

    ADVERTISEMENT