Search code examples
algorithmbig-ocomplexity-theoryexponential

Exponential growth doubling processor speed

According to Wikipedia article on Exponential growth

E.g. if a slow processor can solve problems of size x in time t, then a processor twice as fast could only solve problems of size x+constant in the same time t.

My question is, how do we calculate the constant value that is added to size x. I have seen many pages describing the growth, but nothing around how to calculate this constant. Any ideas?

Thanks,

Solution

  • What the entry says is something like this. Suppose the algorithm is exponential with base c, so that for some input of size x, the running time is

    t ~= cx.

    Now given a processor twice as fast, with an input just a (I'm calling your constant that) larger, the time would again be

    t ~= 0.5 cx + a.

    Dividing the latter by the former, we'd get

    1 ~= 0.5 ca

    or, solving for your constant a,

    a ~= locc(2).

    Don't take this stuff too rigorously. The orders of growth terms just mean that the functions are dominated by these terms. Hence the approx. signs above.