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!
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.
Menu
253
