# Is String's subscript O(n) when given a lot of combining code points?

**URL:** <https://forums.swift.org/t/is-strings-subscript-o-n-when-given-a-lot-of-combining-code-points/67860>\
**Category:** Using Swift\
**Created:** [October 15, 2023, 2:54am UTC](https://forums.swift.org/t/is-strings-subscript-o-n-when-given-a-lot-of-combining-code-points/67860 "2023-10-15T02:54:28Z")\
**Posts on this page:** 1\
**Showing post:** 7

<div class="post-metadata">

**Author:** ![michelf](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/michelf/32/1180_2.png) [@michelf](https://forums.swift.org/u/michelf)\
**Post date:** [October 15, 2023, 12:00pm UTC](https://forums.swift.org/t/is-strings-subscript-o-n-when-given-a-lot-of-combining-code-points/67860/7 "2023-10-15T12:00:54Z")

</div>

> [@Karl](#):
>
> However, it is still independent of the length of the entire string; the same character won't take more time to access if it were part of a longer string. That's what (I think) we mean by O(1) in this context.

All characters together are bounded by the length of the entire string, meaning if you iterate over all characters you don't get O(n^2) behaviour even though there's a nested loop.

But one character can make the entire string, so reading one character of unreasonable length is _at worse_ O(n). It's unlikely to occur in practice outside of maliciously crafted strings, but it's certainly possible to make a couple-of-megabytes character (assuming there is no enforcement of a shorter byte limit).

I made an experiment via the Swift REPL with a gigantic one-character string:

```swift
let s = "a" + String(repeating: "\u{302}", count: 20_000_000)
s.unicodeScalars.count // fast!
s.count // slow! (about one second)
s == "a" // fast!
s.first == "a" // slow! (about one second)
s == "e" // slow! (about half a second)
s.first == "e" // slow! (about one second)
s == "é" // slow! (about half a second)
s.first == "é" // slow! (about one second)
s == "/" // slow! (about half a second)
s.first == "/" // slow! (about one second)

```

Interestingly, `s == "a"` remains fast, but none of the others. I wonder what kind of shortcut it takes that isn't used with `"e"` or `"/"`.

And as a consequence:

```swift
"hello world!".contains(s) // about 10 seconds

```

---

_[View the full topic](https://forums.swift.org/t/is-strings-subscript-o-n-when-given-a-lot-of-combining-code-points/67860)._