Time Complexity

Time complexity describes the amount of time needed to run an algorithm, in terms of the number of elementary operations performed. We use the Big-O Notation (e.g., $O(N)$, $O(N^2)$, $O(N \log N)$) to express time complexity.

We assume elementary operations (e.g., addition/multiplication) have a time complexity of $O(1)$ (constant time).

a = 1;
b = 2;
c = a + b;  // This operation is O(1) time

Our program's runtime is usually dependent on some input, e.g., number of students / array length.

For example, the following algorithm creates a vector with $N$ elements, where $N$ is given in the input. It performs vector assignment, an $O(1)$ operation, for a total of $N$ times. So we say the time complexity of this algorithm is $O(N)$ (linear time).

vector<int> v(n);
for (int i = 0; i < n; i++) {  // The for-loop runs in O(N) time
    v[i] = i;
}

Another example: we want to calculate the sum of $i \times j$ for each $1 \le i, j \le N$.

int s = 0;
for (int i = 0; i < n; i++) {  // This nested for-loop runs in O(N^2) time
    for (int j = 0; j < n; j++) {
        s += i * j;
    }
}

It is possible that our program's runtime depends on multiple inputs. If we modify the last algorithm to calculate the sum of $i \times j$ for each $1 \le i \le N$ and $1 \le j \le M$, then:

int s = 0;
for (int i = 0; i < n; i++) {  // This nested for-loop runs in O(NM) time
    for (int j = 0; j < m; j++) {
        s += i * j;
    }
}

Rules with Big-O Notation

We ignore coefficients and constants in Big-O notation. For example:

int s = 0;
for (int i = 1; i <= 2 * n + 5; i++) s += i;

Even though the loop runs for $2N + 5$ iterations, we still say it is $O(N)$. This is because we only care about the order of magnitude of $N$ involved.

Another example:

int s = 0;
for (int i = 0; i < n; i++) s++;      // O(N)
for (int i = 0; i < n * n; i++) s++;  // O(N^2)

The two for-loops run in $O(N)$ and $O(N^2)$ respectively. Overall, they run in $O(N + N^2) = O(N^2)$. We only preserve the larger term because $N^2 \gg N$ as $N$ becomes large.

Vector

Insertion and deletion are $O(N)$, but push_back and pop_back are $O(1)$. Checking existence of an element via linear search is $O(N)$.

Set

Set is a data structure that allows for faster insertion and deletion (in $O(\log N)$ time where $N$ is the size of the set).

• Set is implemented as a binary search tree (BST), so it does not support random access (but vector does). Random access means being able to access the element in the $k$-th position in $O(1)$ time.
• Elements in a set are unique. To allow for duplicates, use a multiset instead.
• Iteration yields the elements in ascending order.

set<int> s;  // #include <set>

s.insert(1);  // insert, O(log N)
s.insert(2);
s.insert(3);

s.erase(2);  // erase, O(log N)

if (s.find(3) != s.end()) {  // check existence, O(log N)
    cout << "exist\n";
}
// alternatively use s.count(3)

for (int i : s) {  // iteration, O(N)
    cout << i << "\n";
}

Map

The implementation of map is largely similar to set, so the time complexity of each operation is the same. The difference is that map creates a mapping between keys and values, which can function as a lookup table. When we create a map<string, int>, we are specifying that the keys are strings and the values are integers. We assign a key-value pair using m["apple"] = 3 and retrieve the value using the key by m["apple"].

Iteration through a map also follows the ascending order of keys.

map<string, int> m;  // #include <map>

m["apple"] = 3;  // insert, O(log N). "apple" is the key and 3 is the value
m["banana"] = 4;
m["pear"] = 5;

cout << m["apple"] << "\n";  // access, O(log N)
    
m.erase("banana");  // erase, O(log N)

if (m.find("apple") != m.end()) {  // check existence, O(log N)
    cout << "found\n";
}

for (auto [k, v] : m) {  // iteration, O(N)
    cout << k << " " << v << "\n";
}

If we try to access $m[k]$ but $k$ is not already a key in the map $m$, $m[k]$ gets assigned with a "default value" corresponding to the type. In the context of the preceding code, accessing m["grapes"] would assign m["grapes"] = 0 and return 0.