CODEWITHSUNDEEP
arraysswifttime-complexity
nine9
nine9

Reputation: 147

what's the time complexity of swift reversed?

I have read apple developer document:

Array.reverse()

Array.reversed()

the fist article points out: Complexity: O(n), where n is the number of elements in the collection.

the second article points out: Complexity: O(1), and without any reason.

Is that just a little mistake or other reason?

Because second article takes a example for

let word = "Backwards"
for char in word.reversed() {
    print(char, terminator: "")
}
// Prints "sdrawkcaB"

I think O(n) is correct answer. right?

Upvotes: 4

Views: 2322

Answers (2)

OOPer
OOPer

Reputation: 47896

Is that just a little mistake or other reason?

I think O(n) is correct answer. right?

No, reverse() actually takes O(n) and reversed() O(1).

The example is a little bit confusing, but you should better separate it into two parts.

let word = Array("Backwards")
let reversedWord = word.reversed() //<- O(1) is the complexity of this operation.
for char in reversedWord { //<- This for-in loop, of course is O(n)
    print(char, terminator: "")
}
// Prints "sdrawkcaB"

In case of reverse():

var word = Array("Backwards")
word.reverse() //<- This operation takes O(n)
for char in word {
    print(char, terminator: "")
}
// Prints "sdrawkcaB"

Upvotes: 2

David Pasztor
David Pasztor

Reputation: 54755

There is a key importance between the two methods. reverse() mutates the Array in place, so its time complexity has to be O(n) since it needs to exchange the order of all elements.

However, on the other hand, if you check the return type of reversed(), it is ReversedCollection<Array<Element>> and the documentation clearly states that instead of returning a new Array instance, the reversed() method returns a wrapper type that simply contains the original array and provides access to its elements in reverse order. This wrapper type, ReversedCollection can be created in constant time, hence the time complexity of reversed() is O(1).

The example code you mention obviously has O(n) time complexity, since word.reversed() is traversed using a loop, however, the time complexity mentioned in the documentation simply relates to the function call, word.reversed(), which is indeed O(1) for the reasons mentioned above.

Upvotes: 21

Related Questions