Bubblesort -> n -> k1 * n^2 -> x secs Quicksort -> n -> k2 * nlogn -> x * k*(nlogn / n^2) = x * k * (log n / n) where k = k2/k1
You will have to run it on input sets before you can agree on a k. On Nov 24, 2007 4:18 PM, Sherry <[EMAIL PROTECTED]> wrote: > > I calculated times taken to calculate a variety of n values with the > bubble, selection and quick sort. I know that the bubble, selection > are both O(n^2) sorts and that the Quicksort is O(nlogn). But how > could I predict the time taken for these sorts when I know n? > > here is my table for the bubble sort: > Time in milliseconds: > # of # Random Half-Sorted Sorted <---- different data, random is > obviously random data..... > 750 3.1 1.5 1.5 > 1000 6.2 2.8 3.1 > 1500 12.5 6.4 6.3 > 2000 21.9 11.1 10.9 > 2500 35.9 16.7 15.6 > 5000 140.6 64.7 65.6 > 7500 312.5 157.7 172.8 > 10000 559.4 258.5 279.8 > 15000 1306.2 559.0 606.5 > 20000 2312.5 1070.6 1078.7 > > > But how can I compare my actual times (above) with the theoretical > Big > O approximation? This is what confuses me.... > > > Thanks again in advance. :) > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
