> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.
# Time Complexity Analysis
> Learn to analyze your solutions and predict if they'll pass within time limits
# Time Complexity Analysis
## Why This Matters in Competitive Programming
In competitive programming, you have **2-3 seconds** to process up to **10^6** or even **10^8** operations. Before writing a single line of code, you must estimate: **"Will my solution pass?"**
**The Golden Rule**: A modern computer performs about **10^8 simple operations per second**. If your algorithm exceeds this for the given constraints, you'll get **TLE (Time Limit Exceeded)**.
***
## Pattern Recognition: Constraint Analysis
### The Constraint-to-Complexity Table
Memorize this table—it's your first tool for problem-solving:
| Constraint (n) | Max Complexity | Typical Algorithms |
| -------------- | ---------------- | ------------------------------------- |
| n ≤ 10 | O(n!) | Brute force permutations |
| n ≤ 20 | O(2^n) | Bitmask DP, subset enumeration |
| n ≤ 100 | O(n^3) | Floyd-Warshall, 3 nested loops |
| n ≤ 1,000 | O(n^2) | Simple DP, nested loops |
| n ≤ 10^5 | O(n log n) | Sorting, binary search, segment trees |
| n ≤ 10^6 | O(n) | Two pointers, prefix sums, linear DP |
| n ≤ 10^8 | O(log n) or O(1) | Binary search on answer, math |
**Quick Mental Check**: Look at constraints FIRST. If n = 10^5 and you're thinking of O(n^2), stop—you need a better approach.
***
## Step-by-Step Complexity Analysis
### Step 1: Count the Loops
```cpp theme={null}
// O(n) - Single loop
for (int i = 0; i < n; i++) {
// O(1) work
}
// O(n^2) - Nested loops
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// O(1) work
}
}
// O(n * m) - Different bounds
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// O(1) work
}
}
```
### Step 2: Recognize Logarithmic Patterns
```cpp theme={null}
// O(log n) - Halving each iteration
while (n > 0) {
n /= 2; // or n >>= 1
}
// O(n log n) - Loop with halving
for (int i = 0; i < n; i++) {
int x = n;
while (x > 0) {
x /= 2;
}
}
// O(log n) - Binary search
int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (check(mid)) hi = mid;
else lo = mid + 1;
}
```
### Step 3: Identify Amortized Complexity
Some algorithms look slow but are actually fast:
```cpp theme={null}
// Looks like O(n^2), actually O(n)
// Two pointers - each pointer moves at most n times total
int j = 0;
for (int i = 0; i < n; i++) {
while (j < n && arr[j] < arr[i]) {
j++; // j increases, never resets
}
}
// Looks like O(n^2), actually O(n log n)
// Merge sort - each level does O(n), log n levels
void mergeSort(vector& arr, int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r); // O(n)
}
```
***
## Common Complexity Patterns
### Pattern 1: Nested Loops with Dependency
```cpp theme={null}
// What's the complexity?
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) { // j starts from i
// O(1) work
}
}
```
O(n^2). The inner loop runs n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 times.
### Pattern 2: Logarithmic Inner Loop
```cpp theme={null}
// What's the complexity?
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j *= 2) {
// O(1) work
}
}
```
O(n log n). Outer loop: O(n). Inner loop: O(log n) since j doubles each time.
### Pattern 3: Divisor Loop
```cpp theme={null}
// What's the complexity?
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i) {
// O(1) work
}
}
```
O(n log n). This is the harmonic series: n/1 + n/2 + n/3 + ... + n/n = n \* H\_n ≈ n log n.
***
## The CP Complexity Checklist
Before submitting, ask yourself:
What are the input limits? (n, m, q, etc.)
Multiply your complexity by the largest input. Example: O(n^2) with n = 10^5 → 10^10 operations → TLE.
Are you using `map` (log n per operation) or `unordered_map` (O(1) amortized)?
Are you copying vectors/strings in loops?
Stack overflow can occur with recursion depth > 10^6. Use iterative or increase stack size.
***
## Common Pitfalls
### Pitfall 1: String Concatenation
```cpp theme={null}
// O(n^2) - Copying entire string each time!
string result = "";
for (int i = 0; i < n; i++) {
result += s[i]; // Each += is O(length)
}
// O(n) - Use a vector or stringstream
vector result;
for (int i = 0; i < n; i++) {
result.push_back(s[i]);
}
```
### Pitfall 2: Passing by Value
```cpp theme={null}
// O(n) per call - Copies the entire vector
void process(vector arr) { ... }
// O(1) - Pass by reference
void process(vector& arr) { ... }
void process(const vector& arr) { ... } // If not modifying
```
### Pitfall 3: Map vs Unordered\_Map
```cpp theme={null}
// O(log n) per operation
map mp;
mp[x]++; // O(log n)
// O(1) amortized per operation
unordered_map mp;
mp[x]++; // O(1) average
```
**Codeforces Gotcha**: `unordered_map` can be hacked with adversarial inputs causing O(n) per operation. Use custom hash or stick with `map` in critical problems.
***
## Master Theorem (Quick Reference)
For recursive algorithms: T(n) = aT(n/b) + f(n)
| Condition | Complexity |
| ---------------------------------- | ---------------- |
| f(n) = O(n^c) where c \< log\_b(a) | O(n^(log\_b(a))) |
| f(n) = O(n^c) where c = log\_b(a) | O(n^c log n) |
| f(n) = O(n^c) where c > log\_b(a) | O(f(n)) |
**Examples**:
* Merge Sort: T(n) = 2T(n/2) + O(n) → O(n log n)
* Binary Search: T(n) = T(n/2) + O(1) → O(log n)
***
## Practice Problems
### Level 1: Constraint Analysis
1. Given n ≤ 10^6, which complexities will pass in 2 seconds?
* O(n) ✓
* O(n log n) ✓
* O(n^2) ✗
### Level 2: Analyze This Code
```cpp theme={null}
int count = 0;
for (int i = 1; i <= n; i *= 2) {
for (int j = 0; j < n; j++) {
count++;
}
}
```
O(n log n). The outer loop runs log n times, inner loop runs n times each.
***
## Key Takeaways
Always read constraints before thinking about the algorithm.
About 10^8 simple operations per second.
Watch for string copies, map operations, and recursive calls.
With experience, you'll estimate complexity in seconds.
***
## Next Up
Learn input/output optimizations that can mean the difference between AC and TLE.