CODEWITHSUNDEEP
arraysalgorithm
Doug Smith
Doug Smith

Reputation: 29326

Could someone explain to me what this paragraph in The Algorithm Design Manual means? It's confusing me greatly

enter image description here

I just don't understand what it means. It says all queries will be fast, except for those triggering array doubling. Why would an access query trigger a doubling of the array? I've only read that additions when it crosses the capacity mark will trigger them, but if you're accessing a certain element, surely the array has already been doubled to meet that capacity requirement, and accessing it would just be O(n)? What is this paragraph saying?

Upvotes: 1

Views: 90

Answers (1)

Henry
Henry

Reputation: 43758

Your understanding is correct. A mere read access would not cause an array doubling. By the way the complexity for a single access is even O(1) in that case.

It is hard to say what the author meant with "access" without knowing more context of this paragraph.

Upvotes: 2

Related Questions