What does it mean by saying "Asymptotically more efficient"?

Question

What does it mean when we say that an algorithm $X$ is asymptotically more efficient than $Y$ ?

• $X$ will be a better choice for all inputs.
• $X$ will be a better choice for all inputs except small inputs.
• $X$ will be a better choice for all inputs except large inputs.
• $Y$ will be a better choice for small inputs.

---

The link for this question is here .

http://quiz.geeksforgeeks.org/algorithms-analysis-of-algorithms-question-16/

---

I thought that an algorithm more asymptotically efficient should work for all inputs, but I am not getting the reason behind "It works for all inputs except small ones".

Answer 1

First off, both algorithms "work" for all inputs. The question is about performance.

The answers to that question are kind of crappy. One way to say one algorithm is asymptotically more efficient than another is if there is some (problem-specific) input size such that for any larger input size the more efficient algorithm will take fewer "computational steps", usually by some abstract measure, e.g. number of comparisons.

The idea of the answers is that an asymptotically more efficient algorithm may still require more steps before that input size. It can be the case that the asymptotically more efficient algorithm requires fewer steps for all inputs, but it doesn't need to be the case and in practice usually isn't. So a better wording of the "correct" answer would be "$X$ will be a better choice for all inputs except possibly small inputs".

The wording still isn't that great though. First off, many more factors go into deciding what algorithm is a "better choice", but I'll give them that the intent is clear enough in this case. The real issue is "small" and "large". One of my favorite papers is The Fastest and Shortest Algorithm for All Well-Defined Problems. This paper describes an algorithm which given any specification of a function and a proof that it can be computed in polynomial time will compute that function in optimal time complexity within a factor of $5$ plus an additive term. For example, if I provided it an implementation of bubble sort as the function specification and the simple proof that it was $O(n^2)$, it would produce a sorting algorithm that was $O(n\lg n)$. In fact, it would produce an algorithm that was $5cn\lg n + o(n\lg n)$ where $c$ was the constant factor of the asymptotically^* optimal algorithm. This is amazing. There's just one problem: the constant term – hidden in the $o(n\lg n)$ in this example – renders the algorithm almost certainly completely infeasible for virtually any real problem. What do I mean by "completely infeasible"? I mean the heat death of the universe will happen many times over before that algorithm completes. Nevertheless, for suitably "large" inputs it will be faster than bubble sort. My point is it's almost certainly not physically possible to write down by any means a "suitably large" input, let alone compute on it.

At any rate, how I would word the correct answer would be: "$X$ requires fewer steps than $Y$ on sufficiently large inputs". This is still a bit vague as there are multiple notions of "step" that could apply and an algorithm could be asymptotically more efficient by one metric and less efficient by another. This wording avoids the value judgement of "better choice"; there are many reasons to choose asymptotically less efficient algorithms or even less efficient algorithms when constant factors/terms are specified such as cache-efficiency or implementation simplicity.

^* There is a subtlety here. The asymptotically optimal algorithm may have a worse constant factor, $c$, than an asymptotically non-optimal algorithm. I think it will have the best value of $c$ for any asymptotically optimal algorithm, but it's conceivable that to squeeze out a slight gain in asymptotic efficiency, massive complexity is added that significantly increases the constant factor.

Answer 2

"Asymptotically more efficient" means "more efficient for all problems above a certain size". It doesn't say what the "certain size" is, and it doesn't say what happens before that "certain size".

So all the answers except the second one are clearly wrong, because "Asymptotically more efficient" says nothing about small input sizes at all. But the second one is also problematic.

There is currently no hardware that could store an array of $10^{30}$ integers, so clearly $10^{30}$ integers would count as "large input". But I can easily create a sorting algorithm that is asymptotically more efficient than Bubblesort, but only for inputs of $10^{40}$ or more integers. So take answer two, change "large" to "large enough", and it becomes correct.

In practice, it is often a good idea to check for which input size an asymptotically better algorithm is actually faster, and what the required time is for inputs where it is faster, and sometimes an algorithm will only be faster for problem sizes that cannot practically be solved anyway. If algorithm A beats algorithm B, but only for problems where each takes $10^{15}$ years or more, then A isn't very helpful.

Answer 3

What people usually mean when they say something like this is:

If $T_A$ and $T_B$ are the two running-time cost functions of algorithms $A$ and $B$ in model X, respectively, then $T_A \in o(T_B)$.

Many caveats apply here: $X$ needs to be specified, and we have to define what "running-time cost" is to mean, exactly. Time is almost never the subject of investigation. There are many other cost measures. It is unclear if Landau notation makes any helpful statement about efficiency. And so on.

In particular, none of the statements you propose follow, even though people often suggest the second did.

Sadly, the wider community of people dealing with algorithms embraces terminology that borders on vacuous for the sake of simplicity. (Making precise and helpful statements about algorithms is hard!)

You may be interested in our reference questions.

---

An algorithm X is said to be asymptotically better than Y if X takes smaller time than y for all input sizes n larger than a value n0 where n0 > 0.

Note how this is not the usual definition! If $T_A(n) = n+1$ and $T_B(n) = n$, we would not say it's "asymptotically better". Given all the caveats of an analysis that boils down an algorithm's performance down to a single number, no claim that one was "better" than the other can be made.

I recommend you learn computer science from CS resources, not from programmers who have read about stuff on Wikipedia once. (Yes, that's harsh, but I've seen too many falsehoods propagated in programmer circles, even on SO.)

Answer 4

Reason: If two algorithms for the same problem are of the same order then they are approximately as efficient in terms of computation. Algorithm efficiency is useful for quantifying the implementation difficulties of certain problems. • B will be a better choice for all inputs. • B will be a better choice for all inputs except small inputs. • B will be a better choice for all inputs except large inputs. • A will be a better choice for small inputs.