search
Log In
1 vote
798 views

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

in Algorithms 798 views
0
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.$
0
$n^2$ is less efficient than 2n right?
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 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).

0
yes n^2 is less effecient than 2n
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

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

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..!
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.
0
Thanks .. :)

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
667 views
Which of the following is not true about comparison based sorting algorithms? (A) The minimum possible time complexity of a comparison based sorting algorithm is O(nLogn) for a random input array (B) Any comparison based sorting algorithm can be made stable by using ... compared (C) Counting Sort is not a comparison based sorting algortihm (D) Heap Sort is not a comparison based sorting algorithm.
asked Aug 18, 2018 in Algorithms Sumit Singh Chauhan 667 views
3 votes
0 answers
2
613 views
Maximum Subarray Sum problem is to find the subarray with maximum sum. For example, given an array {12, -13, -5, 25, -20, 30, 10}, the maximum subarray sum is 45. The naive solution for this problem is to calculate sum of all subarrays starting with every element and return the ... time complexity using Divide and Conquer. A O(n) B O(nLogn) C O(Logn) D O(n2) Correct answer is B. O(nLogn) How?
asked Jul 27, 2018 in Algorithms Rishav Kumar Singh 613 views
1 vote
1 answer
3
210 views
Consider the following two functions. What are time complexities of the functions? int fun1(int n) { if (n <= 1) return n; return 2*fun1(n-1); } int fun2(int n) { if (n <= 1) return n; return fun2(n-1) + fun2(n-1); } (A) O(2^n) for both fun1() and fun2() (B) O(n) for fun1() and O(2^n) for fun2() (C) O(2^n) for fun1() and O(n) for fun2() (D) O(n) for both fun1() and fun2()
asked Jul 25, 2018 in Algorithms Rishav Kumar Singh 210 views
0 votes
1 answer
4
524 views
Q) Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general? (A) Heap Sort (B) Selection Sort (C) Insertion Sort (D) Merge Sort The Answer Given for This Question is (B). But My question is Why not (D) Since There is not a Single Swap operation is performed in Merge Sort.
asked Jul 8, 2018 in Algorithms pradeepchaudhary 524 views
...