title: Complexity of calling get() on a LinkedList in a for loop using O notation
body: <p>I've a uni practical to determine the complexity of a small section of code using the O() notation.</p>
  
  <p>The code is:</p>
  
  <pre><code>for (int i = 0; i &lt; list.size(); i++)
      System.out.println(list.get(i));
  </code></pre>
  
  <p>The list in question is a linked list. For our practical, we were given a ready made LinkedList class, although we had to write our own <code>size()</code> and <code>get()</code> methods.</p>
  
  <p>What is confusing me about this question is what to count in the final calculation. The question asks:</p>
  
  <blockquote>
    <p>How many lookups would it make if there 100 elements in the list? Based on this, calculate the complexity of the program using O() notation.</p>
  </blockquote>
  
  <p>If I am just counting the <code>get()</code> method, it will make an average of n/2 lookups, resulting in a big O notation of O(n). However, each iteration of the for loop requires recalculating the size(), which involves a lookup (to determine how many nodes are in the linked list).</p>
  
  <p>When calculating the complexity of this code, should this be taken into consideration? Or does calculating the size not count as a lookup?</p>