Algorithm Complexity Analysis

10-page quick guide for Big-O, time, space, cases, and choosing algorithms.

Purpose: a compact 10-page study guide for students who want to recognize, choose, and implement common
algorithm ideas.
How to use it: read one page, trace the example, then solve the quick practice before moving on.

Symbol Meaning

n input size: number of items, characters, nodes, or records

O(...) upper-bound growth rate used to compare algorithms

stable keeps equal items in their original relative order

in-place uses only small extra memory beyond the input array

Algorithm Complexity Analysis Page 1

 1. What Complexity Measures
Complexity analysis predicts how an algorithm grows when the input becomes larger. It ignores machine-specific
details and focuses on the shape of growth.

- Time complexity counts major operations such as comparisons, loop iterations, or recursive calls.
- Space complexity counts extra memory such as arrays, stacks, hash tables, or recursion frames.
- The goal is not exact seconds; it is to compare designs before writing too much code.

Complexity Typical meaning

O(1) constant: direct lookup or fixed number of steps

O(log n) halving the problem repeatedly

O(n) scan each item once

O(n log n) divide and process, common in efficient sorting

O(n^2) nested comparison of many pairs

Quick practice
- For a loop from 0 to n-1, write the time complexity.
- For two nested loops both running n times, explain why the total is n^2.

Algorithm Complexity Analysis Page 2

 2. Counting Loops
Most beginner mistakes happen when reading loops. Count how many times the inner operation runs, then
simplify the expression.

- One loop over n items is usually O(n).

- Two separate loops one after another are O(n + n), simplified to O(n).
- Nested loops multiply: n times n becomes O(n^2).
- A loop that doubles i each time is O(log n) because the value grows very fast.
count = 0
for i in range(n):
for j in range(n):
count += 1
# count is n*n, so time is O(n^2)

Quick practice
- What is the complexity of three separate O(n) loops?
- What is the complexity of for i in range(n): for j in range(10): ?

Algorithm Complexity Analysis Page 3

 3. Best, Average, and Worst Case
The same algorithm can behave differently depending on the input. Always say which case you mean.

- Best case: lucky input, such as finding the target at the first item.
- Worst case: the maximum work, such as scanning the whole list and not finding the target.
- Average case: expected work over typical inputs; it is useful but harder to prove.
- When learning, start by understanding the worst case because it gives a safe upper bound.

Algorithm Common cases

Linear search best O(1), worst O(n)

Binary search best O(1), worst O(log n), but requires sorted data

Quicksort average O(n log n), worst O(n^2) if pivot choices are bad

Quick practice
- Give a best-case input for linear search.
- Why does binary search need sorted data?

Algorithm Complexity Analysis Page 4

 4. Space Complexity
A faster algorithm may need more memory. In real programs, memory use can matter as much as time.

- In-place algorithms modify the input and use little extra memory.
- Auxiliary space excludes the original input but includes extra arrays and recursion stack.
- A recursive function uses memory for each active call.
- Hash tables often turn slow repeated searching into fast lookups, but they use extra memory.
seen = set()
for x in numbers:
if x in seen:
return True
[Link](x)
# Time O(n), extra space O(n)

Quick practice
- Why does merge sort usually need extra space?
- What extra space does iterative binary search use?

Algorithm Complexity Analysis Page 5

 5. Amortized Analysis
Amortized analysis explains operations that are usually cheap but occasionally expensive. The average cost over
many operations can still be small.

- Dynamic arrays sometimes resize and copy all elements.

- A single resize is O(n), but it does not happen every append.
- Over many appends, each item is copied only a small number of times.
- Therefore append to a dynamic array is commonly treated as amortized O(1).

Operation Idea

append usually place item at the end

resize allocate a larger array and copy old items

amortized spread the rare expensive resize over many cheap appends

Quick practice
- Explain why one slow append does not make every append O(n).
- Name another data structure where amortized cost appears.

Algorithm Complexity Analysis Page 6

 6. Recurrence Relations
Recursive algorithms are often analyzed with recurrences: equations that describe work in terms of smaller inputs.

- T(n) = T(n/2) + O(1) describes binary search.

- T(n) = 2T(n/2) + O(n) describes merge sort.
- The recursion tree helps you count work at each level.
- Many divide-and-conquer algorithms have O(log n) levels.
binary_search(a, target, lo, hi):
if lo > hi: return -1
mid = (lo + hi) // 2
if a[mid] == target: return mid
if target < a[mid]: return binary_search(a, target, lo, mid-1)
return binary_search(a, target, mid+1, hi)

Quick practice
- How many times can you halve 64 before reaching 1?
- Which recurrence matches merge sort?

Algorithm Complexity Analysis Page 7

 7. Lower Bounds
A lower bound says no algorithm can do better than a certain amount of work under a model of computation.

- Comparison sorting has a lower bound of Omega(n log n) in the general case.
- Searching an unsorted list needs Omega(n) in the worst case.
- Lower bounds help you stop looking for impossible improvements.
- You can beat a lower bound only by changing assumptions, such as using counting sort for small integer keys.

Problem Typical lower bound

Unsorted search Omega(n) comparisons

Comparison sort Omega(n log n) comparisons

Finding max Omega(n) because every item may matter

Quick practice
- Why must finding the maximum look at every item?
- How can counting sort avoid comparison-sort limits?

Algorithm Complexity Analysis Page 8

 8. Choosing an Algorithm
Algorithm choice depends on input size, data shape, memory, update frequency, and correctness needs.

- For tiny n, simple code can be better than a complex optimized algorithm.
- For sorted data, binary search is much better than linear search.
- For repeated membership tests, use a set or hash table.
- For weighted shortest path with non-negative edges, choose Dijkstra rather than BFS.

Situation Good first choice

Need sorted output merge sort, quicksort, or built-in sort

Need fast membership hash set

Need shortest unweighted BFS

path

Need all-pairs shortest Floyd-Warshall for small dense graphs

paths

Quick practice
- Pick an algorithm for checking duplicate names in a list.
- Pick an algorithm for finding a word in a sorted dictionary.

Algorithm Complexity Analysis Page 9

 9. Common Analysis Pitfalls
Avoid these common mistakes when writing complexity answers in assignments or interviews.

- Do not keep constants: O(2n) becomes O(n).

- Do not keep lower-order terms: O(n^2 + n) becomes O(n^2).
- Do not confuse input value with input size: factoring a number depends on digits, not just the number itself.
- Do not call every recursive algorithm O(log n); branching can make it much bigger.
# This is O(n), not O(2n)
for x in arr: print(x)
for x in arr: print(x)

# This is O(n^2), not O(n^2 + n)

for i in arr:
for j in arr: pass
for x in arr: pass

Quick practice
- Simplify O(5n + 100).
- Simplify O(n^2 + 50n + 7).

Algorithm Complexity Analysis Page 10