Why is the cost of fetching a value in an array, O(1)

Question

I understand why fetching a value from an array using an ordered index is O(1). But suppose you are fetching by value? If the value is the last in array.count == 100, you have to iterate through the whole collection. Wouldn't that be O(n)?

Answer 1

Simple Answer

Locating a value in an array by index is O(1).

Searching for a value in an unsorted array is O(n).

Big O notation

Array is an abstract data structure in computer programming. When discussing Big O notation for an abstract data structure, what we’re asking is: how long does an algorithm take when applied to the abstract data structure given any number of elements. Put another way: how fast is your algorithm as a function of the data within the abstract structure.

Swift Context

This isn’t Machine Code. Swift is a high-level programming language. Meaning Swift code is itself an abstraction from the internal details of the computer it’s running on. So, when we discuss Big O notation for an array in Swift, we aren’t really talking about how it’s stored in memory because we’re assuming the way it’s stored in memory is a reasonable representation of an Array data structure. I think this is important to understand, and it’s why an array in Ruby will be slower than an Array in C for example, because one language is a greater abstraction of the computer it’s running on. We can now move forward knowing the discussion about Big O in the context of a Swift Array is indeed affected by it’s underlying implementation in the computer, but we’re still referring to a perfect version of an instantiated Array when using Big O.

Searching for a value in an unsorted array is O(n)

| 2 | 6 | 10 | 0 |

The above text is a visual representation of an array containing 4 elements.
If I said every time you look at an element, that is a single action with a complexity of 1.
Then I said, I want you to look at each element from left to right only once. What’s the complexity?
4. Good.

STOP.

---

| 2 | 6 | 10 | 0 |

in Swift is:

let array: Array<Int> = [2, 6, 10, 0]

I want you to look at each element from left to right only once.

I am a computer programmer writing Swift, and you are the computer.

for element in array {
    print(element)
}

---

Lets make it more general. Lets say we didn’t know what was inside our array and we named it something… How about book. I now ask: I want you to look at each element from left to right only once. What’s the complexity?
Well, it’s the number of elements in book! Good.
OK Computer. Look at each page in book from left to right until the page has an exclamation point on it. If you find it, show me the page it’s on, if you don’t find it, tell me you didn’t find it. What’s the complexity? Since neither you or I know what page, if any, contains an exclamation point, it’s entirely possible that the very last page is the only page which contains an exclamation point. It’s also possible that none of the pages contain an exclamation point.

The number of pages in our book is n.

In the worst case, whether we find the exclamation point or not, we have to look, at least once, at every single page in book until we find the page with !

O(n)

Bringing it all together in an example

struct Page {
    let content: String
    func contains(_ character: Character) -> Bool {
        return content.contains(character)
    }
    init(_ content: String) {
        self.content = content
    }
}

typealias Book = Array<Page>

let emotionalBook: Book = [Page("this"),
                           Page("is"),
                           Page("a"),
                           Page("simple"),
                           Page("book!")]

let unemotionalBook: Book = [Page("this"),
                             Page("book"),
                             Page("lacks"),
                             Page("emotion.")]

enum EmotionalBook: Error {
    case lacking
}

func findExclamationPoint(within book: Book) throws -> Page {
    //Look at every single page once.
    for page in book {
        if page.contains("!") {
            return page
        }
    }
    //Didn't find a page with ! inside it
    throw EmotionalBook.lacking
}

do {
    //Discovers the last page!
    let emotionalPage = try findExclamationPoint(within: emotionalBook)
    print(emotionalPage.content)
} catch {
    print("This book is \(error) in emotion!")
}

do {
    //Doesn't discover a page, but still checks all of them!
    let emotionalPage = try findExclamationPoint(within: unemotionalBook)
    print(emotionalPage.content)
} catch {
    print("This book is \(error) in emotion!")
}

I hope this helps!

Answer 2

This is the best answer I could find on stackoverflow it self

An array starts at a specific memory address start. An element occupies a certain amount of bytes element_size. The array elements are located one after another in the memory from the start address on. So you can calculate the memory address of the element i with start + i * element_size. This computation is independent of the array size and is therefor O(1). Original answer is here click me