> In that case, wouldn't any implementation be O(1) regardless of whether they use an array, linked list, hashtable, heap, stack, whatever?

Yes, because there is no "n" involved. For example, this code:

  for i in 1...1_000_000 {
      print(i)
  }
  return ["a", "e", "i", "o", "u"].contains(character)

is still O(1), it just has a higher constant factor. The only exception is that you could have psuedo-polynomial algorithms that depend on the value input itself, like

  func foo(i: Int) {
      for _  in 1...i {
          print(i)
      }
  }