What is the amortized time complexity of the 'push' operation for a dynamic array that doubles in size when full?

Show answer

O(1)

While a single push might trigger a resize costing O(n), the total cost of n pushes is O(n) because resizing happens infrequently. Using the aggregate method, the average cost per operation is constant.

Also asked as:

For a dynamic array that doubles in size when full, what is the amortized time complexity of adding an element via 'push'?

Would you remember this in 6 months?

Trivia Forge uses spaced repetition so facts stick. Free, no signup needed.

Turn on Algorithms practice →

More Algorithms trivia

What is the asymptotic time complexity of finding the Longest Common Subsequence of two strings of length m and n using dynamic programming?
Assuming uniform hashing and a constant load factor, what is the average-case time complexity of searching for an element in a hash table whose collisions are resolved by chaining?
What is the lower bound for the height of a binary search tree with n nodes?
What is the lower bound for the worst-case time complexity of any comparison-based sorting algorithm?
What upper bound does a Red-Black Tree with n internal nodes have on its height?
What is the maximum number of nodes in a binary tree of height h, where height is defined as the number of edges on the longest path from the root to a leaf?

See all 83 →