1,314 views
3 votes
3 votes

You are given two sorting algorithms A and B that work in time $O(n \log n)$ and $O(n^2)$, respectively. Consider the following statements:

  1. Algorithm $A$ will sort any array faster than algorithm $B$.
  2. On an average, algorithm $A$ will sort a given array faster than algorithm $B$.
  3. If we need to implement one of the two as the default sorting algorithm in a system, algorithm $A$ will always be preferable to algorithm $B$.


Which of the statements above are true?

  1. I, II and III
  2. I and III
  3. II and III
  4. None of them

1 Answer

2 votes
2 votes

Ans C)

A has sorting time faster than B , generally but not always

Because quick sort differ in worst case running time than merge sort and heap sort

Again Bubble sort, insertion sort has O(n) time complexity in best case , where in other case has O(n2) complexity

So, we cannot say Array A sort any array faster than B

edited by

Related questions

12 votes
12 votes
4 answers
4
go_editor asked May 27, 2016
1,449 views
Let $A$ be an array of $n$ integers, sorted so that $A \leq A \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there exist indices $k$ a...