CODEWITHSUNDEEP
algorithmsortingmathtime-complexitybubble-sort
xodos
xodos

Reputation: 49

How long will take Bubble sort with array of 1 000 000 ints?

Bubble Sort have Computational Complexity O(n^2). So if we have for example CPU 3.5 GHz, these calculation are true? 1 000 000 * 1 000 000 =10^12 3.5 GHz make ~6 000 000 per mike (I think so, please correct me if this is not true)

(10^12/6 * 10^6)/60=~2777 hours This is true?

Upvotes: 1

Views: 8782

Answers (4)

tucuxi
tucuxi

Reputation: 17955

Big-O notation is good when answering the question "as the size of the problem goes up, how does the time/memory needed to solve it grow?". It purposefully ignores all "small" details, and considers an algorithm A that uses 10x (or 100000x - any constant ratio) more time than another algorithm B to be equivalent. In real life, of course, 10x performance does matter. So the 1st problem is that O(n^2) ignores all constant factors (but real-world time does not).

Using the (currently 1st pseudocode example) wikipedia version of Bubblesort:

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n - 1 inclusive do
            if A[i - 1] > A[i] then
                swap(A[i - 1], A[i])
                swapped = true
            end if
        end for
        n := n - 1
    until not swapped
end procedure

you can see that there will be 0 swaps if all elements are initially sorted. Any modern computer implementing this pseudo-code will be able to "sort" an already-sorted array of 1M integers in less than 1 second. So the 2nd problem is that (most implementations, including the above) of bubble-sort are much faster if the array is almost ordered. It so happens that, in real life, arrays are a bit more ordered than what one would expect from a random sampling - which leads to real-world sorting algorithms looking for shortcuts to exploit this.

And of course, the 3rd problem (after looking at what big-O ignores about the code and the exact degree of disorder in the array) has to do with the detailed characteristics of the platform that you execute your code on, and exactly what machine-level instructions you execute on that platform. If, for example, all your data fits into the machine's caches (thus avoiding costly repeated access to main memory), further efficiency can be gained -- at a level that is mostly independent of the algorithm's implementation.

If you look at real-world benchmarks, they specify in full detail all 3 aspects: exact code used, exact data input, and exact compiler & machine architecture. Note that, even then, it is not easy to predict how the run-time will increase as program-size increases, because many transitions will be in the form of steps due to data no longer fitting inside slower memory, rather than smooth increases.

TLDR: the only safe estimate is to measure the time. And it will only answer the question for your implementation, chosen input, & machine. Failing that, you can do several smaller runs, fit a parabola to your data, and extrapolate the result to size 1M: it will not be far off the mark, as 1M ints is not that much.

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59303

A desktop PC these days can do a billion (109) little things in about 5 seconds.

A bubble sort on 106 random ints requires about 1012 little things, or about 5000 seconds = 83 minutes.

This could be off by a factor of 4 or so either way. You would have to write it in a well-compiled language to get that time, since a "little thing" in C++ is much bigger in, .e.g., JavaScript.

Upvotes: 0

Jakob-Go
Jakob-Go

Reputation: 11

It doesn't. Using c++ on an average computer does it in around an hour. Try Benchmarking by using different input values and keep in mind that when you double the amount of ints, the computing time should quadrouple.

Upvotes: 0

Luai Ghunim
Luai Ghunim

Reputation: 976

I think you misunderstood BigO notation.

In theoretical informatics we use BigO to express the upper and lower bound so it does not mean you just plug-in the value and find some time. In-case you don't know with BigO notation O(10N) = O(N).

For example look at the complexity of quicksort, with tilde notation it is ~1.39NlogN and with BigO it's O(NlogN).

BigO or tilde notation has nothing to do with miliseconds. However the only way to know time is by using ratio test.

BigO is used to express number of compares.

Upvotes: 0

Related Questions