School Assignment? Project Due Tomorrow? Chat LIVE With A Programming Expert!

Programming Help

Web Development



What's Here?

  • Members: 307,096
  • Replies: 841,723
  • Topics: 140,663
  • Snippets: 4,467
  • Tutorials: 1,166
  • Total Online: 2,013
  • Members: 140
  • Guests: 1,873

Welcome to Dream.In.Code
Become an Expert!

Join 307,096 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 2,013 people online right now. Registration is fast and FREE... Join Now!




Merge sort

 

Merge sort, Merge sort on lists vs arrays
Tsi

20 Jul, 2009 - 06:43 AM
Post #1

New D.I.C Head
*

Joined: 20 Jul, 2009
Posts: 4



Thanked: 1 times
My Contributions
Hi, this is my first time posting here but I hope anyone can still help me with a little problem I have.

Since dividing an array in the middle takes Theta(1) and dividing a list in the middle takes Theta(n) time. Does merge sort still take the same time (asymptotic) on a list that it does on an array?

Thanks in advance smile.gif

User is offlineProfile CardPM
+Quote Post


sbromley

RE: Merge Sort

20 Jul, 2009 - 07:44 AM
Post #2

New D.I.C Head
*

Joined: 20 May, 2009
Posts: 42



Thanked: 7 times
My Contributions
The answer is yes it takes the same time for a "List" as it does an array. The best case O(n) from an array of length n isn't because its an array or list its because of the steps taken in the algorithm. Best case is actually 2T(n/2) + n = T(n). It comes from breaking down a list into 2 smaller list running the algorithm again and adding the steps to merge.
User is offlineProfile CardPM
+Quote Post

Neumann

RE: Merge Sort

20 Jul, 2009 - 08:20 AM
Post #3

I can judge a book by its cover
Group Icon

Joined: 8 Jul, 2009
Posts: 686



Thanked: 93 times
Dream Kudos: 225
My Contributions
Why would it take Theta(n) to divide a list? They're implemented with arrays, so they will have the same growth.

Edit: sbromley, Merge Sort is not O(n). It is O(n logn). Furthermore, 2T(n/2) + n = T(n) is just an unsolved recurrence relation which you use as a big-O equation, which makes absolutely no sense.

This post has been edited by Neumann: 20 Jul, 2009 - 01:41 PM
User is offlineProfile CardPM
+Quote Post

Tsi

RE: Merge Sort

20 Jul, 2009 - 09:23 AM
Post #4

New D.I.C Head
*

Joined: 20 Jul, 2009
Posts: 4



Thanked: 1 times
My Contributions
Thanks for the answers, they helped smile.gif
User is offlineProfile CardPM
+Quote Post

sbromley

RE: Merge Sort

23 Jul, 2009 - 07:51 AM
Post #5

New D.I.C Head
*

Joined: 20 May, 2009
Posts: 42



Thanked: 7 times
My Contributions
QUOTE(Neumann @ 20 Jul, 2009 - 08:20 AM) *

Why would it take Theta(n) to divide a list? They're implemented with arrays, so they will have the same growth.

Edit: sbromley, Merge Sort is not O(n). It is O(n logn). Furthermore, 2T(n/2) + n = T(n) is just an unsolved recurrence relation which you use as a big-O equation, which makes absolutely no sense.


I was having a tough explaining what I meant, but best case is T(1) = O(1) according to the equation 2T(n/2) + O(n). After that your right that the big O would be O(n log n).

I was trying to explain that it didn't matter how the array was split.

Sorry for any confusion
User is offlineProfile CardPM
+Quote Post

Fast ReplyReply to this topicStart new topic

Time is now: 11/21/09 11:49AM
Invision Power Board v2.1.7 © 2009  IPS, Inc.
Licensed to: MediaGroup1

Live Help!

Be Social

Dream.In.Code RSS Feed Dream.In.Code LinkedIn Group Follow Us On Twitter Fan Us On Facebook

Tutorials

Programming

Web Development

Reference Sheets

Code Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month