time complexity

Question

Q. 13 Which of the following sorting algorithms has every case time complexity? 3

Quick sort
Insertion sort
Selection sort
Bubble sort

Answer 1

Definition of Every Case Time Complexity: "If an algorithm's best-case and worst-case complexity are the same then it has "every-case" complexity" i.e. Algorithm's time complexity does not depend on the input value. 

In the Above

Quick Sort : Best (O(n.log n)) and Worst (O(n^2))

Insertion Sort : Best (O(n)) and Worst (O(n^2))

Selection Sort: Best (O(n^2)) and Worst (O(n^2))

Bubble Sort : Best (O(n)) and Worst (O(n^2))

Hence the answer is C) Selection Sort

Comments

Bubble sort have O(n^2) in best case .

O(n) come only when explicitly in the question says that current pass of bubble sort can compare with previous pass.

---

Dude, check this. 

---

@rude: in this article,they given that "When the list is already sorted (best-case), the complexity of bubble sort is only O(n)".

but,if array is given already sorted then also we can't reduce the comparison we can reduce the swap(for any sorting algo except insertion sort).

why this statement not apply for any other sorting algo like (selection sort).

---

@sourabh Wikipedia page have a algorrithm (pseudo code, we well as implementation). Get a sorted sequence and run that algorithm, you will see that, how it is coming O(n). Do not expect from us to write algorithm and run that for you.

---

Sorry , I think I should edit my notes

---

Dude again you have not check that algorithm. In that algorithm they used a flag variable named swap, if there is no swap takes place in the 1st iteration then it breaks the loop. Because all the elements are in sorted order then there is no swap will take place. Check that once. Its Worth. 

---

But I don't find any break statement in algorithm

---

Check repeat-----until. part in the algorithm. 

Answer 2

Selection sort has time complexity O(n²) in all case .So option C is correct.