I have questions about the worst case and best case run time. I just want to know if the following run times are correct or not and some run times:

Worst case run time:

Merge sort : O(n log n)

Selection sort: O(n^2) // is this correct?

Insertion sort: O(n^2)

Best case run time: // the lowest time the loops will run

Merge sort :

Selection sort:

Insertion sort:

I don't know what the best case run time is. can any tell me what it is and if the worst case run time is correct or not.

## 6 Replies - 2946 Views - Last Post: 10 April 2012 - 04:18 PM

### #1

# Merge Sort, Selection Sort, Insertion Sort run time

Posted 10 April 2012 - 11:40 AM

##
**Replies To:** Merge Sort, Selection Sort, Insertion Sort run time

### #2

## Re: Merge Sort, Selection Sort, Insertion Sort run time

Posted 10 April 2012 - 11:58 AM

The worst case times are correct

If you'd wikipedia'd this, you'd also be able to verify and to check for the best case:

Insertion Sort

Best: O(n)

This is only possible if the list is already sorted. (As there are two phases of the Insertion sort)

Selection Sort

Best: O(n^2)

Merge Sort

Best: O(n log n)

Or O(n)

I think that macosxnerd101 might come here for further elaboration.

If you'd wikipedia'd this, you'd also be able to verify and to check for the best case:

Insertion Sort

Best: O(n)

This is only possible if the list is already sorted. (As there are two phases of the Insertion sort)

Selection Sort

Best: O(n^2)

Merge Sort

Best: O(n log n)

Or O(n)

I think that macosxnerd101 might come here for further elaboration.

This post has been edited by **karabasf**: 10 April 2012 - 12:00 PM

### #3

## Re: Merge Sort, Selection Sort, Insertion Sort run time

Posted 10 April 2012 - 12:10 PM

thanks a lot.

### #4

## Re: Merge Sort, Selection Sort, Insertion Sort run time

Posted 10 April 2012 - 12:45 PM

I have one more question. It is about binary search and sequential search. I want to know the similarities between the run time and the code of the two of them. I know that the both have O(1) as their best case run time but I am not sure about the similarities between the code.

can anyone please tell me a few similarities

can anyone please tell me a few similarities

### #5

## Re: Merge Sort, Selection Sort, Insertion Sort run time

Posted 10 April 2012 - 01:06 PM

I know that binary search divides the array in half until it gets the element it was looking for and that the sequential search searches through the entire list to find the element it was looking for but I just can't think of any similarities in them. A little help would be really appreciated.

### #6

## Re: Merge Sort, Selection Sort, Insertion Sort run time

Posted 10 April 2012 - 02:44 PM

even one similary should be enough

I can't seem to find it anywhere

I can't seem to find it anywhere

I can't seem to find it anywhere

I can't seem to find it anywhere

### #7

## Re: Merge Sort, Selection Sort, Insertion Sort run time

Posted 10 April 2012 - 04:18 PM

anyone I am getting really tired of finding the answer

Page 1 of 1