The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes

What does it mean when we say that an algorithm X is asymptotically more efficient than Y?
(A) X will be a better choice for all inputs
(B) X will be a better choice for all inputs except small inputs
(C) X will be a better choice for all inputs except large inputs
(D) Y will be a better choice for small inputs

Ans given is B, but is it always the case?? At some points it might be true but I do not think this is the case for each and every input..

asked in Algorithms by Active (3k points) | 53 views
yes, B) is ans.

Suppose take two variables $2n$ and $n^{2}$

For small values 1,2 both giving same result

But for big values $n^{2}>>>2n$

So, growth rate of $n^{2}$ is much faster than $2n.$

and $n^{2}$ is more efficient than $2n.$
$n^2$ is less efficient than 2n right?

 Asymptotic notations are generally used for large values and we mainly use big-O notations.

Because when we do it for large values then after a certain point $c$ graphs becomes constant and its easy to choose which algo to use.

For eg:- see this question

After the point c=10000 g1 will perform better than g2, since g1(n)=O(g2(n)) after 10000.

We dont do it for small inputs because the graphs may vary.

like in example above g2 was performing better till n=100 but after that g1 and g2 both were performing same till 10000.

also for smaller inputs the time-space complexity do not matter much. I mean like when we are talking  like

X takes 120 hours and Y takes 110 hours for large inputs

and saying that X takes 5 seconds and Y takes 50 seconds for smaller inputs does not matter much.

we will choose Y. (since Y is more effecient for bigger inputs).

yes n^2 is less effecient than 2n

And moreover say we have two functions whose runtimes are logn and $n^2$ then log n is more efficient than n^2 even for small inputs as well...! So how can B be true in all cases?



I agree with you but it is not true for all cases right?

say for an algo of log n and another of n^2, log n will always be effecient be it small input or large..!

So we will take log n for all the cases like we use binary search(log N) instead of linear search O(N) in sorted arrays.
Then why B ( X will be a better choice for all inputs except small inputs ) is considered true?

we can show that some algorithms having lower time complexity even work best for small cases..!

X is better than Y for large values.

and for small values X may or may not be better. So you are correct.

but it does not matter like i said. In above example difference of 45 seconds is nothing as compared to difference of 10 hours. So thats why we see asymptotic notations for larger values only.
Thanks .. :)

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,540 questions
54,099 answers
71,006 users