-4
$\begingroup$

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

$\endgroup$

closed as unclear what you're asking by Juho, Tom van der Zanden, David Richerby, Luke Mathieson, vonbrand Jul 23 '15 at 2:43

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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
1
$\begingroup$

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?

$\endgroup$

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