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

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

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.

StackExchange Computer Science Q#154041, answer score: 5