Suppose that algorithm A takes 1000n^3 steps and algorithm B takes 2^n steps (Note the carot symbol ^ means raise to the power of which we use here because we c

Question

Suppose that algorithm A takes 1000n^3 steps and algorithm B takes 2^n steps (Note the carot symbol ^ means raise to the power of which we use here because we cannot create the appropriate mathematical symbol in moodle) for a problem of size n. For what size of problem is algorithm A faster than B (meaning algorithm A has fewer steps than B)? describe not only what the answer is but how you arrived at the answer.

Answer 1

For this type of algorithm analysis, some items are very important to note:

  -  there is initial set-up work for each algorithm (much like y-intercept or fixed costs) that is ignored because we are interested in much greater values.

  -  the "steps" that the problem mentions are considered to be "units of work" that are considered to be the same (although for many algorithms they clearly are not); we simply want to estimate how many of them there are.

  -  the usual expression for "takes 1000n^3" includes the words "on the order of" because this is a very rough estimate used for estimating the time or complexity of the computations.

 

Given all that, this is a very simple algebra problem:

   For what value of n is 1000n^3 less than, equal to, and greater than 2^n ?

 

You may use logarithms, calculators, spreadsheets, etc. to solve this (the problem asks you to document your method).

For    0 < n roughly< 24     1000n^3 is greater than 2^n

For    n ≥24                       1000n^3 is less than 2^n             (and becomes very much less than)

 

This estimate is usually sufficient for evaluating or choosing an algorithm.  Use logarithms if a fractional value is needed for the break-even point.

 

To check, use well-known or easy values:

     n         1000n^3                2^n

    10          1000000             1024

    23        12167000        8388608
    24        13824000      16777216

    30        27000000      1.07E+09