Why is vector array doubled?

by

When calculating the average time to insert into a vector, you need to allow for the non-growing inserts and the growing inserts.

Call the total number of operations to insert n items ototal, and the average oaverage.

If you insert n items, and you grow by a factor of A as required, then there are ototal = n + ΣAi [ 0 < i < 1 + lnAn ] operations. In the worst case you use 1/A of the allocated storage.

Intuitively, A = 2 means at worst you have ototal = 2n, so oaverage is O(1), and the worst case you use 50% of the allocated storage.

For a larger A, you have a lower ototal, but more wasted storage.

For a smaller A, ototal is larger, but you don’t waste so much storage. As long as it grows geometrically, it’s still O(1) amortised insertion time, but the constant will get higher.

For growth factors 1.25 ( red ), 1.5 ( cyan ), 2 ( black ), 3 ( blue ) and 4 ( green ), these graphs show point and average size efficiency ( ratio of size/allocated space; more is better ) on the left and time efficiency ( ratio of insertions / operations; more is better ) on the right for inserting 400,000 items. 100% space efficiency is reached for all growth factors just prior to resizing; the case for A = 2 shows time efficiency between 25% and 50%, and space efficiency about 50%, which is good for most cases:

space and time efficiency graph - C like implementations

For runtimes such as Java, arrays are zero filled, so the number of operations to allocate is proportional to the size of the array. Taking account of this gives reduces the difference between the time efficiency estimates:

space and time efficiency graph - Java like implementations

More Related Contents:

  1. How to create the most compact mapping n → isprime(n) up to a limit N?
  2. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  3. Hash table runtime complexity (insert, search and delete)
  4. Data structures for loaded dice?
  5. Find kth smallest element in a binary search tree in Optimum way
  6. How to implement a queue using two stacks?
  7. How do you validate a binary search tree?
  8. design a stack such that getMinimum( ) should be O(1)
  9. Computing set intersection in linear time?
  10. Best algorithm to test if a linked list has a cycle
  11. How to delete in a heap data structure?
  12. Array remove duplicate elements
  13. What is the difference between tree depth and height?
  14. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  15. What is the fastest way to find the closest point to a given point?
  16. insert, delete, max in O(1)
  17. O(klogk) time algorithm to find kth smallest element from a binary heap
  18. Skip List vs. Binary Search Tree
  19. Algorithm for autocomplete?
  20. Hashing a Tree Structure
  21. graph – Dijkstra for The Single-Source Longest Path
  22. How can I return an array of struct in solidity?
  23. The intersection of all combinations of n sets
  24. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  25. Why use binary search if there’s ternary search?
  26. Algorithm for merging two max heaps?
  27. What are probabilistic data structures?
  28. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  29. Given a set of intervals, find the interval which has the maximum number of intersections
  30. How to apply binary search O(log n) on a sorted linked list?

Leave a Comment