English
Menu

Data Structures and Algorithms

A dynamic array, when an element is added while it is full, allocates a new area with twice the capacity and copies all elements into it. If 1,000 elements are added one at a time to an empty array of capacity 1, how many element copies are made in total?

  1. A10
  2. B1,023
  3. C499,500
Show answer and explanation

Answer: B. 1,023

The capacity doubles each time it fills up, going 1, 2, 4, …, 512, and each time all current elements are copied, so the total number of copies is 1 + 2 + 4 + … + 512 = 1,023. For 1,000 additions that is about one copy per element, so the cost per addition is constant on average: amortized O(1). If the capacity grew by only 1 each time, the copies would total 1 + 2 + … + 999 = 499,500, which is O(n²). 10 is the number of reallocations, not the number of elements copied.

  • A. This is the number of reallocations (10, from 1→2 up to 512→1024), not the number of elements copied.
  • B. Correct. 1 + 2 + 4 + … + 512 = 1,023, about one copy per addition on average.
  • C. This is the total number of copies if the capacity grew by 1 each time.
Practice this topic Back to topic

Related calculators

Sorting algorithm visualizerWatch 7 sorting algorithms (bubble, selection, insertion, shell, merge, quick and heap) step by step as bar charts, and compare their comparison and write countsDijkstra's algorithm calculatorCompute shortest paths and distances from a list of weighted edges, and follow each step of finalizing vertices in a table and a diagram

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. For a hash table with many elements kept at a load factor of about 0.5, which is the most appropriate reason that open addressing with linear probing tends to be faster than chaining (linking elements with linked lists)?
  2. Sorting methods with a fixed sequence of compare-exchange steps (sorting networks), such as bitonic sort, are sometimes used for sorting on parallel hardware such as GPUs. Why?
  3. For an array of n elements, what is the time complexity of comparing every pair of distinct elements exactly once (a double loop that compares element i with every element after it, advancing i one step at a time)?
  4. A program with O(n²) time complexity takes 0.5 seconds for 1,000 data items. About how long will it take for 4,000 items?
  5. A linear search compares the elements of an array of 100 distinct values one by one from the front to find a target. If the target is always in the array and is equally likely to be at any position, what is the average number of comparisons?