A solution with O(n) time complexity is always slower than a solution with O(nlog(n)) time complexity even though they have the same space complexity

Question

Why is Solution 1 faster than Solution 2?

The input passed to both solutions:

let myArraySortedSquares = Array(stride(from: -100000, through: 100000, by: 1)).shuffled()

Solution 1 with O(nlog(n)) time complexity and O(n) time complexity

Time elapsed: 2.76 s.

// Time: O(nlog(n)) | Space O(n)
func sortedSquaredArray_solution1(_ array: [Int]) -> [Int] {
    var sortedSquares = Array(repeating: 0, count: array.count)
    
    for (idx, value) in array.enumerated() {
        sortedSquares[idx] = value * value
    }
    return sortedSquares.sorted()
}

Solution 2 with O(n) time complexity & O(n) time complexity

Time elapsed: 6.67 s.

// Time: O(n) | Space O(n)
func sortedSquaredArray_solution2(_ array: [Int]) -> [Int] {
    var sortedSquares = Array(repeating: 0, count: array.count)
    
    var smallerValueIdx : Int = 0
    var largerValueIdx : Int = array.count - 1
    
    for idx in stride(from: array.count - 1, through: 0, by: -1) {
        if abs(array[smallerValueIdx]) > abs(array[largerValueIdx]) {
            sortedSquares[idx] = array[smallerValueIdx] * array[smallerValueIdx]
            smallerValueIdx += 1
        } else {
            sortedSquares[idx] = array[largerValueIdx] * array[largerValueIdx]
            largerValueIdx -= 1
        }
    }
    return sortedSquares
}

The problem:

Write a function that takes in a non-empty array of integers that are sorted in ascending order and returns a new array of the same length with the squares of the original integers also sorted in ascending order.

This is solved. the problem I was using has a shuffled array by mistake, not a sorted one...

I also made a blog posting about it: Algorithms & Data structures, Problem #003

Answer 1

One solution will run in time up to $c_1 n log n$ for some constant $c_1$ if n is large enough. The other solution will run in time up to $c_2 n$ for some $c_2$ is n is large enough.

So you have three problems: First, you don't know which n is "large enough". This formula might only work if $n > 10^{30}$. Second, you don't know how close the actual runtime is to that limit. It might be that for solution 1 the time is one 100th of the formula when n is small, and for solution 2 it is ten times larger when n is small, and only for large n they both get close to the formula. Third, you don't know $c_1$ and $c_2$. If $c_1$ is a tenth of $c_2$, then you would need log n > 10 or n > 1024 for the first formula to actually have a larger value. If $c_1$ is only 1/20th then you would need n > 1 million and so on.

The likely reason why your first solution is faster is that most work is done inside a highly optimised implementation of sortedArray, and the Swift standard library has an implementation that is linear when you sort either a sorted array or the concatenation of two sorted arrays, in either ascending or descending order. (You can also sort in linear time if your array is created by taking a sorted array of n elements, and inserting and changing at most O (n / log n) array elements).

From a software development point of view, the first version is much preferable because it is simpler and works for arbitrary functions, not only squares. On the other hand it is likely slower if the sorting method doesn't have this optimisation for sorting sorted arrays.

Answer 2

The big O time notation is a way to talk about relative time behavior of different algorithms as n approaches infinity. Shooting towards infinity is a trick that allows us to ignore the constant parts of the time behavior, and the lower-level factors.

In the real world of course your n will not be anywhere close to infinity, and often its quite small. So yes, you will often find a simpler algorithm with a theoretically worse O() time behavior will outperform a complex one with a better O() on your real-world data with limited n sizes.

Notice how much simpler the code for your nlogn algorithm is? Its 4 lines of code, vs. 10.

Here's an example graph they use on the Big O Wikipedia page to illustrate the concept mathematically. Two functions of different O() levels are plotted in red and blue. After about x=4.5, the y values will forever be lower for the red function, with the gap ever increasing. However, before that point the constants on the lower factors predominate, and the two functions are quite comparable, with the blue function often returning smaller y values.

The proper way to look at these things experimentally of course isn't to just try both out with a single "n" input size. Double your "n" and see what you get. Then double it again. Keep doing that until it takes one algorithm (probably your nlogn one) annoyingly long to complete.

Answer 3

A likely explanation is the hidden constant. We can assume the following empirical formulas for the running times: c.n.log(n) and d.n.

Then it is possible that c.log(200000) < d, for instance due to the parts of the code that are interpreted and those using precompiled functions.