Swift Array reversed() function O(1) complexity?

user_3608824 0
Viewed 555

We can reverse an Array in Swift using reversed function, here's the example:

let numbers = [3, 5, 7]
let reversedNumbers = Array(numbers.reversed())
print(reversedNumbers)
// Prints "[7, 5, 3]"

Here's the link :Array reversed()

At the end of the discussion part, it says Complexity O(1), I believe this is about time complexity, how can reverse an array take O(1) time?

reverse swift arrays
1 Answers

Actually reversed() returns an object with wrapper over the original array not actual reversion of the contents hence O(1).

If you check the return type of reversed() call it is ReversedCollection which internally keeps original collection as _base unless its contents are modified. Basically ReversedCollection is just presenting/returning elements of its base collection in the reverse manner to save time and memory.

Following example shows that reversed array remains same as the original array unless it is modified:

var originalArray = [1, 2, 3]
var reversedArray = originalArray.reversed()

print("0th index of OriginalArray \(originalArray[0])")
print("0th index of ReversedBaseArray \(reversedArray._base[0])")


print("0th index of OriginalArray \(originalArray.first)")
print("0th index of ReversedBaseArray \(reversedArray.first)")

originalArray[0] = 4 // Modification makes a separate copy of each instance
print("0th index of OriginalArray \(originalArray[1])")
print("0th index of ReversedBaseArray \(reversedArray._base[1])")


// Console Output:
// 0th index of OriginalArray 1
// 0th index of ReversedBaseArray 1


// First element of OriginalArray Optional(1)
// First element of ReversedBaseArray Optional(3)


// 0th index of OriginalArray 4
// 0th index of ReversedBaseArray 1
user_15246240
Related