The Gateway to Computer Science Excellence

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

0

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

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

0

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 *g*1(*n*)=*O*(*g*2(*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).

0

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?

0

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

0

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.

0

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

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

+1

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.

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,229 answers

197,978 comments

104,566 users