CODEWITHSUNDEEP
algorithmsortingtime-complexityquicksortmergesort
JohnnyBoi
JohnnyBoi

Reputation: 35

How does the runtime of an algorithm and the input size tell you the time complexity of the algorithm?

I did an experiment calculating the mean runtime for sorting algorithms merge sort and quick sort for arrays of size n, and I'm not sure how to prove merge sort and quicksort are O(log2(n)) from the results.

Results are here:

n       mergeSort:       # mergeSort:    quickSort:      quickSort
        mean runtime     mean runtime/   mean runtime    mean runtime/
        (nanosecs)       (n*log2(n))     (nanosecs)      (n*log2(n))
10      49833           1500            17048           513             
100     31245           47              58956           88              
1000    363917          36              158396          15              
10000   2050911         15              1306825         9               
100000  15513647        9               13075212        7               
1000000 183957966       9               153438217       7               
2000000 376220756       8               317621177       7

I noticed that mean run time divided by n*log2(n) seems to become constant as n increases, so does that mean that the that time complexity becomes closer to nlog2(n) as n increases?

Upvotes: 0

Views: 488

Answers (2)

user1196549
user1196549

Reputation:

Generally speaking, you cannot check the complexity of an algorithm (and even less prove it) by benchmarking.

Because it takes a large N before the low order terms of the time function become neglectible and the asymtotic behavior really shows up. And at the same time large N breaks the common hypothesis of constant time memory accesses. On modern machines, this hypothesis doesn't hold at all.

For your data, on a plot you can't tell a linear law from a linlog law.

enter image description here

Upvotes: 1

rcgldr
rcgldr

Reputation: 28911

For a basic 2 way merge sort, the number of moves is n ⌈log2(n)⌉, but the number of compares varies depending on the data, but time complexity will be O(n log(n)) with variation in the constant. Quick sort runtime can be greatly affected by the data, and based on your numbers, I assume you're testing psuedo random data.

There will be an increase in runtime once the array becomes so large that cache locality becomes an issue. There are also variations of merge sort and quick sort that affect the run time. For smaller arrays, bottom up merge sort is a bit faster than top down, due to top down's overhead of pushing and popping pairs of indices for run boundaries to and from the stack. Far larger arrays, most of the time is spent in the merge part, which can be identical for top down and bottom up merge sort.

Upvotes: 0

Related Questions