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

#1 myname123   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-April 12

Merge Sort, Selection Sort, Insertion Sort run time

Posted 10 April 2012 - 11:40 AM

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.

Is This A Good Question/Topic? 0
  • +

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

#2 karabasf   User is offline

  • D.I.C Regular
  • member icon

Reputation: 202
  • View blog
  • Posts: 417
  • Joined: 29-August 10

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.

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

Was This Post Helpful? 0
  • +
  • -

#3 myname123   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-April 12

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

Posted 10 April 2012 - 12:10 PM

thanks a lot.
Was This Post Helpful? 0
  • +
  • -

#4 myname123   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-April 12

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
Was This Post Helpful? 0
  • +
  • -

#5 myname123   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-April 12

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.
Was This Post Helpful? 0
  • +
  • -

#6 myname123   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-April 12

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
Was This Post Helpful? 0
  • +
  • -

#7 myname123   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-April 12

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
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1