1

I've always wondered about why this is the case.

For instance, say I want to find the number 5 located in an array of numbers. I have to compare my desired number against every other single value, to find what I'm looking for. This is clearly O(N).

But, say for instance, I have an index that I know contains my desired item. I can just jump right to it right? And this is also the case with Maps that are hashed, because as I provide a key to lookup, the same hash function is ran on the key that determined it's index position, so this also allows me to just then, jump right to it's correct index.

But my question is why is that any different than the O(N) lookup time for finding a value in an array through direct comparison?

As far as a naive computer is concerned, shouldn't an index be the same as looking for a value? Shouldn't the raw operation still be, as I traverse the structure, I must compare the current index value to the one I know I'm looking for?

It makes a great deal of sense why something like binary search can achieve O(logN), but I still can't intuitively grasp why certain things can be O(1).

What am I missing in my thinking?

3
  • I thought I understood everything until "It makes a great deal of sense why something like binary search can achieve O(logN)". As I read the question, it looks like you're asking why by-index lookup is not O(n), why does O(log n) for binary search make sense to you then? Mar 21, 2014 at 19:03
  • Because binary search makes occasional naive comparisons, but it used the knowledge from each comparison to eliminate half of the search space. If I'm looking for index 6, in an array of indexes 0..9, as a dumb computer when traversing the array, how do I know whether I'm currently at index 0 or 9 or 6 without doing a direct comparison for each index. Which to me seems the exact same thing as doing direct comparison for index values. Mar 21, 2014 at 19:10
  • Ah, this question is not about databases? I was pretty sure it is :) Mar 24, 2014 at 6:32

2 Answers 2

2

Arrays are usually stored as a large block of memory.

If you're looking for an index, this allows you to calculate the offset that that index will have in this block of memory in O(1).

Say the array starts at memory address 124 and each element is 10 bytes large, then you can know the 5th element is at address 124 + 10*5 = 174.

Binary search will actually (usually) do something similar (since by-index lookup is just O(1) for an array) - you start off in the middle - you do a by-index lookup to get that element. Then you look at the element at either the 1/4th or 3/4th position, which you need to do a by-index lookup for again.

1
  • Now this is much more satisfying. I don't have extensive hardware knowledge, but if the reason pertains to knowing "how far to run ahead" from starting index based off desired index, so it's right at the correct index by the time it makes the comparison. That I think conceptually makes more sense. Mar 21, 2014 at 21:20
0

A HashMap has an array underneath it. When an key/value pair is added to the map. The key's hashCode() is evaluated and normalized so that its value can be placed in its special index in the array. When two key's codes are normalized to belong to the same index of the map, they are appended to a LinkedList

When you perform a look-up, the key you are looking up has its hash code() evaluated and normalized to return an index to search for the key. It then traverses the linked list you find the key and returns the associated value.

This look-up time is the same, in the best case, as looking-up array[i] which is O(1)

The reason it is a speed up is because you don't actually have to traverse your structure to look something up, you just jump right to the place where you expect it to be.

3
  • But this still doesn't answer my question about how the raw operation, of traversing a set of indexes until you find the one you are looking for is any different than O(N) for doing direct value comparison search in an array. I can see clearly how O(logN) is able to be achieved in various scenarios. O(1) still doesn't seem clear, but would be more clear if maybe it varied, but for all intensive purposes it was O(1). Mar 21, 2014 at 19:00
  • Brute-force Search and traversal are synonymous. They both have worst case time complexity of O(n). Lookup is different as it involves looking for something in the place you expect it to be.
    – Brian
    Mar 21, 2014 at 19:03
  • But my fundamental source of confusion comes from the fact that I don't see how a computer can expect anything without doing direct comparison. If I tell it to go lookup the value from index 6, how could it possibly know when it's at index 6 without either doing a direct comparison as it traverses indexes, or does something like binary search? To me that seems fundamentally like the same complexity of operation as doing index lookup vs. value lookup. Mar 21, 2014 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.