Explore BrainMass

Explore BrainMass

    Big O - algorithm comparison

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

    Suppose program A takes (2^n)/1000 units of time and program B takes 1000(n^2) units. For what values of n does program A take less time than program B.

    I am really looking for a detailed explanation on this problem - to check my answer.


    © BrainMass Inc. brainmass.com March 4, 2021, 6:03 pm ad1c9bdddf

    Solution Preview

    Ta = 2^n/1000; Tb = 1000*(n^2)

    If Ta < Tb,

    2^n/1000 < 1000*(n^2)
    (2^n)/n^2 < 1,000,000
    Take log on both sides,

    n*log 2 - 2log n < 6

    n < (6 + 2logn)/log ...

    Solution Summary

    This solution helps with a problem about algorithm comparison.