GEEKSFORGEEKS ALGO

Question

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..

Comments

@srestha

@Satbir

help.!

---

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 https://gateoverflow.in/2466/gate1994-1-23

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?

---

@Satbir

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..!

---

see

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 .. :)