The study of Time Complexity examines how long it will take for a operation to complete given a input size of n. For example, inserting an item in the middle of a QLinkedList takes the same amount of time, regardless of the size of the list. However, inserting an item in the middle of a QVector can be very slow if the QVector contains many items.

To describe algorithmic complexity the following terminology is used and is based on the "big O" notation.

• Constant time: O(1). A function is said to run in constant time if it requires the same amount of time no matter how many items are present in the container.
  One example is QLinkedList::insert().
  
  
• Logarithmic time: O(log n). A function that runs in logarithmic time is a function whose running time is proportional to the logarithm of the number of items in the container.
  
  
• Linear time: O(n). A function that runs in linear time will execute in a time directly proportional to the number of items stored in the container.
  One example is QVector::insert().
  
  
• Linear-logarithmic time: O(n log n). A function that runs in linear-logarithmic time is asymptotically slower than a linear-time function, but faster than a quadratic-time function.
  
  
• Quadratic time: O(n²). A quadratic-time function executes in a time that is proportional to the square of the number of items stored in the container.

The following table summarizes the algorithmic complexity of the sequential container classes. The notation of amortized behavior O(1) means if you call the function only once you might get O(n) behavior, however if you call it multiple times (e.g., n times) the average behavior will be O(1).

The following table summarizes the algorithmic complexity of the associative container classes.

With QVector, QHash, and QSet, the performance of appending items is amortized O(log n). It can be brought down to O(1) by calling QVector::reserve(), QHash::reserve(), or QSet::reserve() with the expected number of items before inserting the items.

Growth Strategies

QVector<T>, QString, and QByteArray store their items contiguously in memory. QHash<Key, Val, Hash, KeyEqual> maintains a hash table whose size is proportional to the number of items in the hash. To avoid reallocating the data every time an item is added at the end of a container, these classes allocate extra memory each time the container needs to grow.

For most applications the default growing algorithm will be enough. If you need more control QVector<T>, QHash<Key, Val, Hash, KeyEqual>, QSet<T>, and QByteArray provide three methods which allow checking and specifying how much memory to allocate.

capacity()

returns the number of items which can be stored without the need to reallocate

QHash and QSet return the number of buckets in the hash table

reserve(size)

explicitly preallocates memory for size items

squeeze()

frees any memory not required to store the items

If you know the approximate number of items stored in a container, start by calling reserve(). When you are done populating the container call squeeze() to release the extra preallocated memory.