Suppose that we say: 

LinkedList<Integer> lst = ...;
int sum = 0;
for (int i = 0; i < lst.size(); i++ )
    sum += lst.get(i);

What is the Big O of this code?

  • A: O(1)
  • B: O(n)
  • C: O(n log n)
  • D: O(n2)
  • E: O(n3)

    Answer: D

    Because LinkedList requires stepping down the list to find the requested element, the .get(i) operation is O(i). Since i is growing within the loop, this sets up a Bermuda Triangle situation, giving a time of O(n2).

    Contents    Page-10    Prev    Next    Page+10    Index