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 similar to the one used by Quinn's “smart” train in HW4.

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 I did the analysis of Quinn's train, I noticed that the worst case got rarer and rarer. Most of the time adding a package to the smart train didn't cause a reallocation of all thre packages to a new train. 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?

  • Hedgehog speaking

    I didn't like trying to explain why Quinn couldn't go bankrupt. I didn't feel like I had the right words to explain it.

  • LHS Cow speaking

    Actually you both have good points, and that's what today's lesson is about!

(When logged in, completion status appears here.)