Suppose that we say: 

Cons lst = append(x, y);
and that x has length n and y has length m.

What is the Big O of this statement?

  • A: O(n)
  • B: O(m)
  • C: O(n + m)
  • D: O(n) + O(m)
  • E: O(n2 + m2)

    Answer: A

    append makes a copy of the first input list, and reuses the second input list. Therefore, its Big O depends only on the size of the first input. The Big O is O(n) because the first input list is copied, one element at a time.

    Contents    Page-10    Prev    Next    Page+10    Index