Time and Space Complexity

Algorithms are often measured by how efficiently they run. Two key metrics for this are time complexity and space complexity. Time complexity helps us understand how the running time of an algorithm increases with the size of the input, while space complexity measures how much extra memory an algorithm uses.

Basic Operation Count

Even though different computers may execute the same algorithm at different speeds, and real running times are hard to calculate exactly, we can estimate performance by counting the number of basic operations the algorithm performs. Basic operations include arithmetic operations (addition, subtraction, multiplication, division), variable access (for fundamental data types), and assignment operations. By estimating the count of these operations, we can gauge the algorithm's efficiency without getting bogged down by machine-specific details.

Time Complexity

Definition

When we talk about how “fast” an algorithm is, we must consider how its running time increases with the size of the input. This input size can refer to the number of elements in a list, the number of vertices in a graph, the number of edges, etc. Generally, as the input size grows, the run time increases. In practice, we are less focused on the time required for a specific input size and more interested in the trend of the growth – this trend is what we call the time complexity of the algorithm.

Why Focus on the Trend?

There are several reasons to focus on the time trend rather than exact timings:

1. Modern computers can execute hundreds of millions of basic operations each second. As a result, we often deal with very large input sizes. For example, suppose we have two algorithms:

   • Algorithm A runs in time proportional to $100n$.
   • Algorithm B runs in time proportional to $n^2$.

   For very small inputs (say, when $n < 100$), Algorithm B might be faster. However, if we allow a longer execution time, Algorithm A can handle much larger inputs compared to Algorithm B. This is why the growth trend with respect to $n$ is more important than the constant factors when input sizes are huge.

2. Counting basic operations abstracts away the machine-specific differences in execution time. Although different operations (like addition versus division) take different amounts of time, when we analyze time complexity, we ignore these differences along with constant factors. This approach simplifies the analysis and gives a clear picture of the algorithm's scalability.

Time complexity is often analyzed in two ways:

• Worst-case time complexity: The upper limit on the running time for any input of size $n$. This is most common in competitive programming, where the algorithm must handle every possible input within a given range.
• Average (expected) time complexity: The expected running time averaged over all inputs of size $n$, assuming a random distribution of inputs.

In essence, time complexity is a measure of how the running time grows with increasing input size, and we formalize this concept using asymptotic notations.

Asymptotic Notations

Asymptotic notations provide a formal way to express the growth rates of functions while ignoring lower-order terms and constant factors. The most common notations are as follows:

• Uppercase symbols (or non-strict inequalities) include equals within their definition, while lowercase symbols (or strict inequalities) do not. For instance, the notation $\Theta$ is used when an expression is tightly bounded from above and below, whereas $O$ is used for an upper bound and $\Omega$ for a lower bound. The notations $O$ and $o$ come from the Greek letter Omicron, representing similar ideas of “small” and “big.”

Big Theta (Θ) Notation

We write

if and only if there exist positive constants $c_1, c_2$ and $n_0$ such that for all $n \ge n_0$,

This means $f(n)$ is bounded both above and below by the function $g(n)$ multiplied by some constants. For example,

Big O (O) Notation

If we are only interested in an upper bound, then we use:

if and only if there exist positive constants $c$ and $n_0$ such that for all $n \ge n_0$,

In many analyses, especially when focusing on the worst-case scenario, we use $O$ notation.

Big Omega (Ω) Notation

Conversely, to express a lower bound we write:

if and only if there exist positive constants $c$ and $n_0$ such that for all $n \ge n_0$,

Little o (o) Notation

When we need a strict upper bound (ignoring the possibility of equality), we use:

if and only if for every positive constant $c$, there exists an $n_0$ such that for all $n \ge n_0$,

Little omega (ω) Notation

Similarly, to express a strict lower bound, we write:

if and only if for every positive constant $c$, there exists an $n_0$ such that for all $n \ge n_0$,

Useful Properties

• $f(n) = \Theta(g(n))$ if and only if $f(n)=O(g(n))$ and $f(n)=\Omega(g(n)).$
• $f_1(n) + f_2(n) = O(\max(f_1(n), f_2(n))).$
• $f_1(n) \times f_2(n) = O(f_1(n) \times f_2(n)).$
• For any constant $a \neq 1$, $\log_a{n} = O(\log_2 n).$
  (Using the change-of-base formula, all logarithms grow at the same rate asymptotically, so we generally omit the base in complexity discussions.)

Simple Examples of Time Complexity Calculation

For Loops

Consider the following Python example that contains three nested loops:

n = int(input())
m = int(input())
for i in range(n):
    for j in range(n):
        for k in range(m):
            print("hello world")

If we treat the input values $n$ and $m$ as our problem size, the running time of this code is proportional to the number of loop iterations, which is $\Theta(n^2 m)$.

Depth-First Search (DFS)

When performing a DFS on a graph with $n$ vertices and $m$ edges, each vertex and each edge is visited a constant number of times. As a result, the overall time complexity of DFS is $\Theta(n + m)$.

What Counts as a Constant?

When analyzing time complexity, it’s important to determine which variables are considered part of the input size. For instance, consider the following code snippet:

N = 100000
for i in range(N):
    print("hello world")

If the value of $N$ is fixed and not part of the problem's variable input, then this loop runs in constant time, or $O(1)$. In complexity analysis, any value that does not scale with the input is treated as a constant factor (effectively counted as 1).

It’s important to note that theoretical discussions assume an algorithm can process any input size. Thus, precomputing answers for every possible input within a limited range doesn’t actually reduce an algorithm’s complexity to $O(1)$ when the input size might potentially be unbounded.

The Master Theorem

The Master Theorem is a handy tool for quickly determining the time complexity of many recursive algorithms. Consider a recurrence of the form

then:

The intuition behind this theorem is that at each level of the recursion, a problem of size $n$ is divided into $a$ subproblems of size $\frac{n}{b}$, with an additional work of $f(n)$ done at that level. Summing the work done across all levels of the recursion tree leads to the overall complexity.

Let’s look at a few examples:

1. For the recurrence

   $$T(n) = 2T\left(\frac{n}{2}\right) + 1,$$

   we have $a=2$, $b=2$, and $\log_2 2=1$. Since the added work $f(n)=1$ grows slower than $n^{\log_b a} = n$, the Master Theorem tells us that $T(n) = \Theta(n)$.

2. For the recurrence

   $$T(n) = T\left(\frac{n}{2}\right) + n,$$

   we have $a=1$, $b=2$, and $\log_2 1=0$. Here, the work $f(n)=n$ dominates, so we conclude that $T(n) = \Theta(n)$.

3. For

   $$T(n) = T\left(\frac{n}{2}\right) + \log n,$$

   with $a=1$ and $b=2$ (so $\log_2 1=0$), the work is $f(n)=\Theta(\log n)$. In this case, the Master Theorem yields $T(n)=\Theta(\log^2 n)$.

4. Finally, for

   $$T(n) = T\left(\frac{n}{2}\right) + 1,$$

   again with $a=1$ and $b=2$, we find that $T(n) = \Theta(\log n)$.

Amortized Complexity

In some cases, while a single operation might be costly, most operations are cheap, leading to a low average or amortized cost. For a deeper introduction to this topic, see additional resources on amortized analysis.

Space Complexity

Just as we analyze running time, we can look at how an algorithm’s memory requirements grow with the input. Space complexity measures the additional memory needed relative to the size of the input, providing insight into the algorithm’s efficiency beyond just execution speed.

Computational Complexity

Although this article focuses on analyzing algorithms from an efficiency perspective, there is a broader field called computational complexity that dives deeper into the intrinsic difficulty of computational problems. Exploring that subject can provide further insights into how and why certain problems are hard to solve.

This tutorial has introduced the core concepts behind analyzing algorithm efficiency, including time complexity, space complexity, and asymptotic notations. With these tools, you'll be better equipped to compare algorithms and understand the trade-offs underlying different approaches.