CS 70

Before You Start

Recall the array-backed list structure that we discussed a few weeks ago (you can review this page) and saw in the IntVector class in HW5. At a high level, an array-backed list stores the list items in an array. When performing a push_back operation, there are two possibilities:

  • If there is room in the array, simply put the item in the next open spot.
  • If the array is full, allocate a new, larger array, and copy all the list items to the new array.

This approach is exactly what you used for your CoordVector class in HW4 (and also saw in the IntVector class in HW5).

What is the most accurate and precise way to characterize the best-case complexity of push_back() for an array-backed list?

What is the most accurate and precise way to characterize the worst-case complexity of push_back() in an array-backed list?

  • Duck speaking

    I said it's \( \mathrm{O}(n) \), is that okay?

  • LHS Cow speaking

    That's a true statement, but it's imprecise. \( \mathrm{O}(n) \) means “no worse than linear time”, which suggests that performance could be better (e.g., constant time).

  • RHS Cow speaking

    Here we are specifically characterizing the worst-case complexity, and in the worst case, push_back() definitely takes linear time! So \( \Theta(n) \) is more precise, because it says that the worst-case complexity is no worse than linear time and no better than linear time.

Given the above analyses, what is the most accurate and precise characterization we currently have of the overall complexity of push_back() for an array-backed list?

  • Dog speaking

    You know, I can't help thinking that calling push_back() \( \mathrm{O}(n) \) is kinda missing something. When we were thinking about CoordVector and IntVector and how they doubled the capacity whenever it ran out, I noticed that the worst case (copying everything) got rarer and rarer. Most of the time push_back() didn't cause a reallocation of all the array elements. So I think it's more accurate to say that push_back() is \( \mathrm{O}(n) \) in the worst case, but \( \Theta(1) \) most of the time. Is there a way to say that?

  • LHS Cow speaking

    That's what today's lesson is about!

(When logged in, completion status appears here.)