Note 1
Foundations

Before getting into different techniques and methods, let’s discuss fundamental topics including time complexity and basic DSA.

1.1 Time Complexity

One of the primary goal of competitive programming and an effective program is efficiency. Indeed most, if not all, programming competitions have time limits, which varies for each language. Some problems can be solved with brute force approach while others need an elegant solution to fit in the given time frame.

Please note that the definition above is very basic, and not formal. A more formal definition involves theoretical computer science, and maybe I can include more on the formal definition and P = NP in other notes.

The approximate number of the operations for the worst-case is represented using the big O notation. The lower the complexity, the efficient the program is.

The six major complexities are Constant \(\mathcal {O}(1)\), Linear \(\mathcal {O}(n)\), Logarithmic \(\mathcal {O}(n \log n)\), Quadratic \(\mathcal {O}(n^2)\), Exponential \(\mathcal {O}(2^n)\), and Factorial \(\mathcal {O}(n!)\) [CS02-8]. We will evaluate the time complexities of algorithms as we walk through them, but here are some simple examples using input/output and loops.

A simple hello world example have constant time complexity since it only prints once. One the other hand, the following snippet

1for (int i = 0; i < 5*n; i++) { 
2    // constant time code 
3}

is \(\mathcal {O}(n)\) [CS02-2]. When we start nesting them, it gets horrible. For instance, the following snippet is \(\mathcal {O}(nm)\).

1for (int i = 0; i < n; i++) { 
2    for (int j = 0; i < m; j++) { 
3        // constant time code 
4    } 
5}

Naturally, we can see that we get quadratic time if we nest code as the following.

1for (int i = 0; i < n; i++) { 
2    for (int j = 0; i < n; j++) { 
3        // constant time code 
4    } 
5} 
6for (int i = 0; i < 10000*n; i++) { 
7    // constant time code 
8}

The snippet above is \(\mathcal {O}(nn) = \mathcal {O}(n^2)\). Note that the time complexity is not linear since the big O is only interested in the worst case.

One more thing to note is the order of growth. Consider the graph below [CS02-8].

From the graph above, we can see that some functions grow faster than the other. For instance, the constant time has the lowest growth rate since it is not growing at all. Next, we can see that \(\log {n}\) grows slower than \(n\), which grows slower than \(n \log {n}\) [CS02-5]. Generally speaking, anything below \(\mathcal (n)\) is good while we really want to avoid anything beyond the linear time.

Now big O is important since it is used to compare two algorithms that perform the same task. With asymptotic analysis, we can evaluate and compare algorithms without the inconsistency of inputs and machines [CS02-5]. This was a short introduction to computing time complexities and big O notation. In the next section, we will be discussing fundamental data structures.