Fundamentals of Computational Complexity

1Introduction

This lecture explains how to evaluate growth in running time and memory use as the input size increases. Rather than relying only on elapsed seconds measured on a particular computer, asymptotic growth permits analysis of an algorithm as inputs become large.

2Input Size and Computational Resources

The {input size} $$n$$n is a nonnegative integer that measures the scale of a problem instance. An appropriate measure depends on the problem: a one-dimensional array may use its number of elements, whereas a two-dimensional array may require both its numbers of rows and columns. Not every input is therefore adequately described by a single parameter.

{Time complexity} is a function describing how the number of executed basic operations grows with input size. {Space complexity} is a function describing growth in memory required during execution. When the analysis excludes storage occupied by the input itself and counts only additional storage, the measure is called {auxiliary-space complexity}.

3Variation among Inputs

Inputs of the same size can require different amounts of a resource.

• {Best-case complexity} is the minimum resource use among inputs of size $$n$$n.
• {Worst-case complexity} is the maximum resource use among inputs of size $$n$$n.
• {Average-case complexity} is the expected resource use under a specified probability distribution on inputs of size $$n$$n.

Average-case complexity is undefined until the probability distribution is specified. Moreover, best, average, and worst cases classify inputs, whereas $$O$$O, $$\mathrm{\Theta }$$\Theta, and $$\mathrm{\Omega }$$\Omega describe asymptotic relations between functions. These are separate concepts.

4Asymptotic Notation

Let $$f\left(n\right)$$f(n) and $$g\left(n\right)$$g(n) be nonnegative for all sufficiently large $$n$$n.

• $$f\left(n\right)=O\left(g\right(n\left)\right)$$f(n)=O(g(n)) means that positive constants $$c,n_0$$c,n_0 exist such that $$f\left(n\right)\text{[PARSE ERROR: Undefined("Command("le")")]}cg\left(n\right)$$f(n)\le c g(n) for every $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}{n}_0$$n\ge n_0. It states an asymptotic upper bound.
• $$f\left(n\right)=\mathrm{\Omega }\left(g\right(n\left)\right)$$f(n)=\Omega(g(n)) means that positive constants $$c,n_0$$c,n_0 exist such that $$cg\left(n\right)\text{[PARSE ERROR: Undefined("Command("le")")]}f\left(n\right)$$c g(n)\le f(n) for every $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}{n}_0$$n\ge n_0. It states an asymptotic lower bound.
• $$f\left(n\right)=\mathrm{\Theta }\left(g\right(n\left)\right)$$f(n)=\Theta(g(n)) means that both $$f\left(n\right)=O\left(g\right(n\left)\right)$$f(n)=O(g(n)) and $$f\left(n\right)=\mathrm{\Omega }\left(g\right(n\left)\right)$$f(n)=\Omega(g(n)) hold. It states equality of asymptotic growth rates up to constant factors.

Thus, $$O$$O denotes an upper bound and does not necessarily assert a tight growth rate. For example, $$3n+5=O\left(n^2\right)$$3n+5=O(n^2) is true, but $$3n+5=\mathrm{\Theta }\left(n\right)$$3n+5=\Theta(n) is more precise.

5Examples

Let $$T\left(n\right)=3n+5$$T(n)=3n+5. For $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$$n\ge 1,

so $$T\left(n\right)=\mathrm{\Theta }\left(n\right)$$T(n)=\Theta(n). Constant terms and constant factors do not alter the asymptotic growth rate.

For linear search on an array of length $$n$$n, a match at the first element gives a best-case running time of $$\mathrm{\Theta }\left(1\right)$$\Theta(1), while a match only at the final element or no match gives a worst-case running time of $$\mathrm{\Theta }\left(n\right)$$\Theta(n). By contrast, binary search on a sorted array halves the candidate interval at each comparison. After $$k$$k comparisons, at most $$n/2^k$$n/2^k candidates remain, yielding a worst-case running time of $$\mathrm{\Theta }\left(\log \right(n+1\left)\right)$$\Theta(\log(n+1)), including the empty-array case.

An algorithm that only reads its input and uses a fixed number of variables has auxiliary-space complexity $$\mathrm{\Theta }\left(1\right)$$\Theta(1). Allocating another array of length $$n$$n requires $$\mathrm{\Theta }\left(n\right)$$\Theta(n) auxiliary space. Time and space must be analyzed separately.

6Connections to Subsequent Lectures

The next lecture derives the time and auxiliary-space complexity of recursion from the number of recursive calls and the maximum call depth. The subsequent sorting and search lectures compare applicability conditions, correctness, and complexity together.

7Summary

• Input size must be defined by a measure appropriate to the problem.
• Time and space complexity measure different computational resources.
• Best, average, and worst cases classify inputs; $$O$$O, $$\mathrm{\Theta }$$\Theta, and $$\mathrm{\Omega }$$\Omega describe asymptotic relations between functions.
• $$O$$O gives an upper bound, $$\mathrm{\Omega }$$\Omega gives a lower bound, and $$\mathrm{\Theta }$$\Theta gives a matching upper and lower bound.