Data structure - Big O of access and indexing. What do they really mean?

Question

I found two articles online:

First

Second

What confuses me is the terms Indexing and Access they use. Are they referring to the same thing?

Take Array as an example:

The first says Big O of Access is O(1). The second says Big O of Indexing is O(1). So I assume they are both saying given an index x, you can get the value of array[x] in O(1).

Take Hash Table as an example:

The first says Big O of Access is N/A. I think it's because with a Hash Table, you only do searching by a key. You don't retrieve a value by an index. But the second says Big O of Indexing is O(1). Maybe it's referring to searching this time?

Now take Binary Tree as an example:

The first: Access is O(logN). The second: Indexing is O(logN).

What?

So now they are both referring to searching? You can't retrieve a value from a Binary Tree by an index, right?

Please help me to gain some clarification. Thanks!

Answer 1

In the above articles indexing and Access are meant to be the same thing, they both describe the asymptotic complexity required to have access at an element.

More specifically:

• In arrays, indexing or Access is of course O(1) when talking about accessing for example 3rd element, and searching is O(n) due to linear pass required in worst case.
• In Hashtables it is well pointed that we can't refer to indexing e.g what is the 3rd element- this question has no point. First article says N/A taking into consideration the above notice. The second article considers Hashtable - indexing to be finding an element (where you know the hash key of the element). Then it is true that finding an element if you have a good hashtable (good length and of most important good hash function) it is almost consant time O(1).
• In binary trees finding - searching an element is O(logn). Here the first article by using the word accessing, is referred to searching an element as you have well pointed that out. You can't retrieve a value from a Binary Tree by an index, but second article by indexing it means searching since indexing in other case wouldn't mean anything. Note that searching ( or accessing or indexing or searching) in binary search trees is not O(logn) but O(n) because imagine the case in which we insert sorted elements in tree (e.g 1,2,3,4,5,...) then the tree becomes a list and searching is linear. Many times it is referred that it is O(logn) because the case where the elements are sorted is vary rare and most times it takes O(logn)(but this is asymptotic complexity of average case and not worst! ). You would get O(logn) if you use AVL trees where the tree is always balanced and searching is O(logn).

So in Hashtables and binary search trees in the above articles accessing-indexing is referred as searching.