Data structure - Big O of access and indexing. What do they really mean?
<p>I found two articles online:</p>

<p><a href="http://bigocheatsheet.com/" rel="noreferrer">First</a></p>

<p><a href="https://gist.github.com/TSiege/cbb0507082bb18ff7e4b" rel="noreferrer">Second</a></p>

<p>What confuses me is the terms <strong>Indexing</strong> and <strong>Access</strong> they use. Are they referring to the same thing?</p>

<p>Take <strong>Array</strong> as an example:</p>

<p>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 <code>x</code>, you can get the value of <code>array[x]</code> in O(1).</p>

<p>Take <strong>Hash Table</strong> as an example:</p>

<p>The first says Big O of Access is N/A. I think it's because with a Hash Table, you only do <strong>searching</strong> 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 <strong>searching</strong> this time?</p>

<p>Now take <strong>Binary Tree</strong> as an example:</p>

<p>The first: Access is O(logN). The second: Indexing is O(logN).</p>

<p>What?</p>

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

<p>Please help me to gain some clarification. Thanks!</p>