How would I solve these problems involving time complexity:

  1. Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n$, insertion sort runs in $8n^2$ steps, while merge sort runs in $64n \log_2 n$ steps. For which values of $n$ does insertion sort beat merge sort?

  2. What is the smallest value of n such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?

  3. For each function $f(n)$ and time $t$ , determine the largest size $n$ of a problem that can be solved in time $t$, assuming that the algorithm to solve the problem takes $f(n)$ microseconds.

    (a) $n! = 1$ second

    (b) $n \log_2 n$ = 1 second

  • 5
    $\begingroup$ Have you attempted to actually calculate any of the answers, all of them just require you to solve one or two equations. You could even just use excel and some graphs. $\endgroup$ – Luke Mathieson Nov 3 '12 at 5:16

Problems comparing the time complexity of different algorithms are usually concerned with asking which algorithm takes less time (that is, less steps). So when the problem asks which one is "beats" the other or is "faster" for a given size of input $n$, it is asking which would take less steps (and hence less time); i.e. which would result in a smaller number.

In the context of your problems, some algorithms will outperform others for small $n$ (in terms of time) but be outperformed for large $n$. The questions ask for the size $n$ at which it insersects/switches.

How would you determine that intersection point?

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.