The Central Idea
Two algorithms may both be correct and terminating while behaving very differently as the input grows.
Complexity analysis asks:
- How does the amount of work grow with input size?
- How does memory use grow with input size?
- Which parts of the algorithm dominate for large inputs?
Input Size
Complexity is expressed in terms of an input-size parameter.
This parameter is often written
\[ n. \]Depending on the problem, \(n\) might mean:
- the number of entries in a list;
- the number of vertices in a graph;
- the number of digits in an integer;
- the number of symbols in a string;
- the number of candidate objects.
Input Size Must Match the Problem
For graph algorithms, one parameter may not be enough.
We often use:
\[ V=\text{number of vertices} \]and
\[ E=\text{number of edges}. \]Then a graph-traversal complexity can naturally be written in terms of both \(V\) and \(E\).
Time Complexity
Time complexity describes how the number of computational steps grows with input size.
It does not usually mean literal seconds.
Instead, we count representative operations such as:
- comparisons;
- assignments;
- arithmetic operations;
- array accesses;
- edge examinations;
- recursive calls.
Why Count Operations Instead of Seconds?
Actual execution time depends on:
- processor speed;
- programming language;
- compiler;
- memory system;
- implementation details;
- other system activity.
Operation counts provide a machine-independent model of algorithmic growth.
A Simple Linear Loop
Suppose an algorithm examines every entry of a list once.
For \(n\) entries, it performs approximately
\[ n \]basic examinations.
The running time therefore grows linearly with \(n\).
Constant Time
An operation takes constant time when the amount of work does not grow with input size.
Examples may include:
- reading one known array position;
- comparing two numbers;
- adding two machine-sized values;
- swapping two stored entries.
Constant growth is written
\[ O(1). \]Linear Time
If work grows proportionally to \(n\), we describe the algorithm as linear.
\[ O(n). \]Linear search has worst-case linear time because it may inspect all \(n\) entries.
Quadratic Time
Nested processing of all pairs often produces quadratic growth.
For example, if an outer loop repeats \(n\) times and an inner loop also repeats \(n\) times, the total number of inner operations is approximately
\[ n\cdot n=n^2. \]This gives
\[ O(n^2). \]Cubic and Higher Polynomial Growth
Three nested \(n\)-step loops can lead to
\[ O(n^3). \]More generally,
\[ O(n^k) \]for fixed \(k\) is called polynomial time.
Logarithmic Time
Repeatedly reducing a problem by a fixed multiplicative factor often produces logarithmic growth.
Binary search repeatedly halves the active interval:
\[ n,\quad \frac n2,\quad \frac n4,\quad \frac n8,\ldots. \]The number of halvings is about
\[ \log_2 n. \]Therefore, binary search has worst-case time
\[ O(\log n). \]Linearithmic Time
A common important growth rate is
\[ n\log n. \]Algorithms such as merge sort achieve this pattern.
The \(n\) factor may represent work across one recursion level, while the \(\log n\) factor represents the number of levels.
Exponential Time
An algorithm may have exponential growth such as
\[ O(2^n). \]A complete include-or-exclude search over \(n\) independent items has \(2^n\) possible subsets.
Exponential growth becomes large very quickly.
Factorial Time
Algorithms that examine every permutation of \(n\) distinct objects may require work proportional to
\[ n!. \]Factorial growth is even faster than ordinary exponential growth.
A Useful Growth Hierarchy
For large \(n\), a common ordering is:
\[ 1 \ll \log n \ll n \ll n\log n \ll n^2 \ll n^3 \ll 2^n \ll n!. \]The symbol \(\ll\) here means "grows much more slowly than."
Asymptotic Analysis
Asymptotic analysis studies algorithm behavior as the input size becomes large.
It emphasizes dominant growth rather than small-input details.
Big-O Notation
Big-O notation gives an asymptotic upper bound.
Informally,
\[ T(n)=O(g(n)) \]means that, for sufficiently large \(n\), the growth of \(T(n)\) is bounded above by a constant multiple of \(g(n)\).
Formal Big-O Definition
We write
\[ T(n)=O(g(n)) \]if there exist positive constants \(c\) and \(n_0\) such that
\[ 0\le T(n)\le c\,g(n) \]for all
\[ n\ge n_0. \]Ignoring Constant Factors
Suppose
\[ T(n)=7n. \]The factor \(7\) does not change the asymptotic growth category.
Therefore,
\[ \boxed{T(n)=O(n)}. \]Ignoring Lower-Order Terms
Suppose
\[ T(n)=3n^2+8n+12. \]For large \(n\), the \(n^2\) term dominates.
Thus,
\[ \boxed{T(n)=O(n^2)}. \]Big-O Is an Upper Bound, Not Necessarily an Exact Rate
If an algorithm runs in
\[ O(n), \]then it is also technically true that it runs in
\[ O(n^2). \]But \(O(n)\) is the more informative upper bound.
Big-Omega Notation
Big-Omega gives an asymptotic lower bound.
\[ T(n)=\Omega(g(n)) \]means that \(T(n)\) grows at least as fast as a constant multiple of \(g(n)\) for sufficiently large \(n\).
Big-Theta Notation
Big-Theta gives an asymptotically tight bound.
\[ T(n)=\Theta(g(n)) \]means that \(T(n)\) is both
\[ O(g(n)) \]and
\[ \Omega(g(n)). \]Its growth is bounded above and below by constant multiples of \(g(n)\).
Example of Theta
If
\[ T(n)=5n+20, \]then
\[ \boxed{T(n)=\Theta(n)}. \]Linear growth is both an upper and lower asymptotic description.
Best-Case Complexity
Best-case complexity describes the least work required among inputs of a given size.
In linear search, if the target is the first entry, only one comparison is needed.
Thus the best case is
\[ O(1). \]Worst-Case Complexity
Worst-case complexity describes the greatest work required among valid inputs of a given size.
In linear search, the target may be last or absent.
Then all \(n\) entries may be examined:
\[ \Theta(n). \]Average-Case Complexity
Average-case complexity describes expected work under a specified probability model for inputs.
An average-case statement is incomplete unless the underlying distribution or assumption is clear.
Expected Complexity
Randomized algorithms may be analyzed using expected running time.
The expectation is taken over random choices made by the algorithm, possibly together with an input distribution.
Expected time and worst-case time are different guarantees.
Counting Loop Iterations
Consider:
\[ i=1,2,\ldots,n. \]The loop executes \(n\) times.
If each iteration takes constant time, then
\[ T(n)=\Theta(n). \]Two Consecutive Loops Add
Suppose one loop performs \(n\) operations and a second performs \(2n\) operations.
The total is
\[ n+2n=3n. \]Therefore,
\[ \boxed{\Theta(n)}. \]Nested Loops Multiply
Suppose an inner loop runs \(n\) times for each of \(n\) outer iterations.
The total is
\[ n\cdot n=n^2. \]Therefore,
\[ \boxed{\Theta(n^2)}. \]Triangular Loops
Some nested loops do not perform exactly \(n^2\) iterations.
Suppose the inner loop performs
\[ 1,2,3,\ldots,n \]operations across successive outer iterations.
Then the total is
\[ 1+2+\cdots+n=\frac{n(n+1)}2. \]Triangular Growth Is Still Quadratic
Since
\[ \frac{n(n+1)}2 = \frac12n^2+\frac12n, \]the dominant term is \(n^2\).
Therefore,
\[ \boxed{\Theta(n^2)}. \]Doubling Loops
Suppose a loop updates
\[ i\leftarrow2i \]starting at \(i=1\) and stopping once \(i>n\).
The values are
\[ 1,2,4,8,\ldots. \]The number of iterations is
\[ \Theta(\log n). \]Halving Loops
A loop that repeatedly replaces
\[ n\leftarrow\left\lfloor\frac n2\right\rfloor \]also executes logarithmically many times.
Multiplicative shrinking produces logarithmic iteration counts.
Recursive Complexity
Recursive algorithms often lead to recurrence relations for running time.
For example, binary search satisfies approximately
\[ T(n)=T\left(\frac n2\right)+c. \]This leads to
\[ \Theta(\log n). \]Merge Sort Recurrence
Merge sort satisfies approximately
\[ T(n)=2T\left(\frac n2\right)+cn. \]There are two half-size recursive calls and linear merging work.
The resulting growth is
\[ \boxed{\Theta(n\log n)}. \]Recursion Tree Intuition
A recursion tree helps organize recursive work by levels.
For merge sort:
- there are about \(\log n\) levels;
- the total merge work per level is about \(n\).
Multiplying gives
\[ n\log n. \]Naive Fibonacci Recursion
Direct recursive Fibonacci repeatedly solves the same subproblems.
The recursion tree branches heavily, creating exponential growth.
Memoization changes the structure by ensuring that each distinct state is solved only once.
Dynamic Programming Complexity
A useful first estimate is
\[ \boxed{ \text{time} \approx (\text{number of states}) \times (\text{work per state}) }. \]If there are \(n\) states and each requires constant work, time is often
\[ \Theta(n). \]Two-Dimensional Dynamic Programming
A table with \(n\) rows and \(m\) columns contains
\[ nm \]states.
Constant work per state gives
\[ \Theta(nm) \]time.
Graph Traversal Complexity
Using adjacency lists, BFS and DFS run in
\[ \Theta(V+E). \]Each vertex is processed a bounded number of times, and each edge is examined a bounded number of times.
Representation Can Change Complexity
If the same graph is stored in an adjacency matrix, scanning all possible neighbors of every vertex may require
\[ \Theta(V^2) \]work.
Data representation is part of algorithm analysis.
Sorting Complexity
Selection sort performs
\[ (n-1)+(n-2)+\cdots+1 \]comparisons.
Therefore, its comparison count is
\[ \Theta(n^2). \]Insertion Sort Complexity
Insertion sort may perform very little movement when data is already nearly sorted.
Its best-case behavior can be linear, while its worst-case behavior is quadratic:
\[ O(n) \]best case and
\[ O(n^2) \]worst case under standard implementations.
Comparison Sorting and \(n\log n\)
Efficient general comparison-based sorting algorithms commonly achieve
\[ \Theta(n\log n) \]time.
A deeper result shows that comparison sorting has an \(\Omega(n\log n)\) worst-case lower bound.
This explains why \(n\log n\) appears so often as a benchmark for efficient comparison sorting.
Amortized Analysis
Sometimes one operation is occasionally expensive, but a long sequence of operations has low average cost per operation.
Amortized analysis spreads occasional expensive work across many cheaper operations.
It provides a deterministic sequence-level guarantee rather than a probability-based average.
Example of Amortized Thinking
A dynamic array may occasionally need to allocate a larger storage block and copy many entries.
Most insertions do not require resizing.
Across many insertions, the average cost per insertion can remain constant in an amortized sense.
Space Complexity
Space complexity describes how memory requirements grow with input size.
Memory may be used for:
- variables;
- arrays;
- tables;
- queues;
- stacks;
- recursive call frames;
- temporary output structures.
Input Space Versus Auxiliary Space
Sometimes we distinguish the memory needed to store the input from the extra memory used by the algorithm.
Auxiliary space means additional working memory beyond the input itself.
Constant Auxiliary Space
An algorithm that uses only a fixed number of variables may require
\[ O(1) \]auxiliary space.
The amount of extra storage does not grow with \(n\).
Linear Auxiliary Space
If an algorithm creates an extra array of \(n\) entries, its auxiliary space is
\[ O(n). \]Merge sort commonly uses linear additional storage for merging.
Recursive Stack Space
Recursive calls require stack frames.
If recursion depth is \(d\) and each frame uses constant space, stack space is approximately
\[ O(d). \]Binary Search Stack Space
Recursive binary search has recursion depth
\[ O(\log n). \]Therefore, its recursive stack usage is
\[ O(\log n). \]An iterative implementation can reduce auxiliary stack usage to
\[ O(1). \]Recursive Factorial Stack Space
Recursive factorial decreases \(n\) by \(1\) per call.
Its recursion depth is
\[ O(n). \]Therefore, the call stack may use
\[ O(n) \]auxiliary space.
Dynamic Programming Space
A table with \(n\) stored states uses
\[ O(n) \]space.
A two-dimensional \(n\times m\) table uses
\[ O(nm) \]space.
Space Optimization
If a recurrence uses only a few previous states, the entire table may not need to remain in memory.
For Fibonacci, only the previous two values are needed.
Storage can therefore be reduced from
\[ O(n) \]to
\[ O(1). \]Time-Space Tradeoffs
Sometimes extra memory can reduce running time.
Memoization stores results so they do not need to be recomputed.
In other situations, using less memory may require repeated computation.
This is a time-space tradeoff.
Preprocessing Tradeoffs
An algorithm may spend time organizing data before later queries.
Sorting a collection may cost
\[ O(n\log n), \]but repeated later searches may then use
\[ O(\log n) \]binary search.
Up-front work can reduce future work.
Dominant Terms
Suppose
\[ T(n)=4n^3+20n^2+7n+100. \]For large \(n\), the cubic term dominates.
Therefore,
\[ \boxed{T(n)=\Theta(n^3)}. \]Why Constants Still Matter in Practice
Asymptotic notation ignores constant factors, but real implementations do not.
An \(O(n)\) algorithm with a large constant may be slower than an \(O(n\log n)\) algorithm for small enough \(n\).
Asymptotic analysis describes long-run growth, not every practical detail.
Crossovers
Different algorithms can become preferable at different input sizes.
For small inputs, a simple quadratic method may outperform a more elaborate \(n\log n\) method because of lower overhead.
For large inputs, the better growth rate usually becomes decisive.
Exact Counts Versus Asymptotic Counts
Exact analysis may produce a formula such as
\[ \frac{n(n-1)}2. \]Asymptotic analysis summarizes the same growth as
\[ \Theta(n^2). \]Both are useful, but they answer different levels of detail.
Complexity Is a Property of an Algorithm and Model
Complexity is not determined by the mathematical problem alone.
Different algorithms for the same problem may have different complexity.
The assumed cost model and data representation also matter.
Common Error: Treating Big-O as Exact Equality
The statement
\[ T(n)=O(n^2) \]does not mean
\[ T(n)=n^2. \]Big-O describes an asymptotic upper bound, not an exact operation count.
Common Error: Keeping Constant Factors in Big-O
The expressions
\[ O(5n) \]and
\[ O(n) \]describe the same asymptotic class.
Common Error: Keeping Lower-Order Terms
The expression
\[ O(n^2+n+1) \]is normally simplified to
\[ \boxed{O(n^2)}. \]Common Error: Automatically Multiplying Consecutive Loops
Consecutive loops add their costs.
Nested loops multiply iteration counts.
Confusing these structures can change a linear estimate into an incorrect quadratic one.
Common Error: Assuming Every Nested Loop Is \(O(n^2)\)
Loop bounds may depend on different variables or change geometrically.
A nested loop might have complexity
\[ O(nm), \] \[ O(n\log n), \]or another form.
Count the actual iteration structure.
Common Error: Ignoring Input Representation
BFS with adjacency lists has
\[ O(V+E) \]time.
A matrix-based representation may lead to
\[ O(V^2) \]neighbor scanning.
Representation can materially change complexity.
Common Error: Confusing Worst Case and Average Case
A worst-case guarantee applies to every input of the specified size.
An average-case statement depends on a probability model.
They should not be reported as if they were the same claim.
Common Error: Ignoring Recursive Stack Space
A recursive algorithm may use little explicit storage but still consume substantial memory through call frames.
Recursion depth must be included in auxiliary-space analysis.
Common Error: Assuming Faster Always Means Better
An algorithm with lower time complexity may:
- use more memory;
- be more complex to implement;
- have larger constants;
- require stronger input assumptions.
Complexity is one important part of algorithm selection, not the only part.
A Reliable Procedure for Time-Complexity Analysis
- Define the input-size parameter or parameters.
- Choose a representative basic operation.
- Count how often that operation occurs.
- For loops, analyze their iteration bounds.
- For nested loops, determine whether costs multiply or have dependent ranges.
- For recursion, write a recurrence or use a recursion tree.
- Identify best, worst, or average case when relevant.
- Keep the dominant growth term.
- Remove constant factors in asymptotic notation.
- State the resulting bound clearly.
A Reliable Procedure for Space-Complexity Analysis
- Identify memory required for the input.
- Identify additional arrays, tables, queues, stacks, or maps.
- Determine the maximum simultaneous size of each structure.
- Include recursive call-stack depth.
- Distinguish total space from auxiliary space when useful.
- Keep the dominant asymptotic term.
- Check whether storage can be reused or compressed.
Example: Consecutive Loops
Suppose an algorithm performs one loop of \(n\) iterations followed by one loop of \(n^2\) iterations.
The total work is
\[ n+n^2. \]The dominant term is \(n^2\), so
\[ \boxed{\Theta(n^2)}. \]Example: Mixed Nested Loop
Suppose an outer loop executes \(n\) times while the inner loop repeatedly doubles a variable until it exceeds \(n\).
The inner loop requires
\[ \Theta(\log n) \]iterations per outer iteration.
Therefore, the total is
\[ \boxed{\Theta(n\log n)}. \]Example: Space for BFS
BFS maintains a visited structure and a queue.
In the worst case, these may collectively store information proportional to the number of vertices.
Thus auxiliary space is commonly
\[ O(V). \]Example: Backtracking Search
Suppose \(n\) independent choices are binary.
The search tree can have up to
\[ 2^n \]complete leaves.
Thus worst-case time may be exponential:
\[ O(2^n). \]But if recursion depth is at most \(n\), the current-path stack may use only
\[ O(n) \]space.
Practice 1: Linear Loop
A loop performs one constant-time operation for each of \(n\) list entries. What is its time complexity?
Practice 2: Nested Loops
An outer loop runs \(n\) times and an inner loop runs \(n\) times for each outer iteration.
What is the resulting complexity?
Practice 3: Repeated Halving
A problem size is halved on each step until it reaches \(1\).
What growth rate describes the number of steps?
Practice 4: Simplify Big-O
Simplify
\[ O(4n^3+7n^2+12). \]Practice 5: Consecutive Loops
One loop takes \(\Theta(n)\) time and a later loop takes \(\Theta(n^2)\) time.
What is the total asymptotic time?
Practice 6: Graph Traversal
What is the standard adjacency-list time complexity of BFS or DFS in a graph with \(V\) vertices and \(E\) edges?
Practice 7: Dynamic-Programming Table
A table has \(n\) rows and \(m\) columns, and each state takes constant time to compute.
What is the time complexity?
Practice 8: Recursive Stack
A recursive algorithm has maximum recursion depth \(n\) and uses constant memory per call.
What is its stack-space complexity?
Practice 9: Time-Space Tradeoff
Why can memoization use more memory while reducing running time?
Practice 10: Growth Comparison
Which grows more slowly for large \(n\):
\[ n\log n \]or
\[ n^2? \]Practice Answers
Practice 1
\[ \boxed{\Theta(n)}. \]Practice 2
\[ n\cdot n=n^2, \]so the complexity is
\[ \boxed{\Theta(n^2)}. \]Practice 3
\[ \boxed{\Theta(\log n)}. \]Practice 4
The cubic term dominates:
\[ \boxed{O(n^3)}. \]Practice 5
\[ \Theta(n)+\Theta(n^2)=\boxed{\Theta(n^2)}. \]Practice 6
\[ \boxed{\Theta(V+E)}. \]Practice 7
\[ \boxed{\Theta(nm)}. \]Practice 8
\[ \boxed{O(n)}. \]Practice 9
Memoization stores subproblem answers so repeated states can be retrieved instead of recomputed. The stored table uses memory, but it can eliminate a large amount of duplicate work.
Practice 10
For large \(n\),
\[ \boxed{n\log n} \]grows more slowly than
\[ n^2. \]What to Remember
- Time complexity measures how computational work grows with input size.
- Space complexity measures how memory requirements grow.
- Asymptotic analysis emphasizes dominant growth for large inputs.
- Big-O gives an upper bound, Big-Omega a lower bound, and Big-Theta a tight bound.
- Constant factors and lower-order terms are omitted in asymptotic classification.
- Common growth rates include \(1\), \(\log n\), \(n\), \(n\log n\), \(n^2\), \(2^n\), and \(n!\).
- Consecutive costs add; nested repeated costs often multiply.
- Recursive complexity can be analyzed with recurrences and recursion trees.
- Auxiliary space includes temporary structures and recursive call stacks.
- Faster time can require more memory, creating time-space tradeoffs.
The most important habit is: identify what grows with the input, count the dominant work or storage, and describe that growth rather than focusing only on one specific execution.
Where We Go Next
Complexity analysis compares how exact algorithms consume resources. But not every computational problem is best approached by an exact, deterministic procedure.
The next lesson, Exact, Approximate, and Randomized Algorithms, compares algorithms that guarantee exact answers with methods that trade precision or determinism for speed, scalability, or practical tractability.