A slow but correct idea is usually easy to find. The real work is a fast enough idea. Time complexity estimates how running time grows with the input size n, so you can reject an approach before implementing it.
Slow par sahi idea aksar aasaan hota hai — asli kaam hai kaafi fast idea dhundhna. Time complexity batati hai ki input size n badhne pe time kaise badhta hai, taaki tum kisi approach ko implement karne se pehle hi reject kar sako.
2.1Calculation rules
- Loops: k nested loops over the input give O(nᵏ).
- Order of magnitude: constants and lower-order terms disappear. Loops running 3n, n + 5 or ⌈n/2⌉ times are all O(n), and a loop over pairs
j > i(n(n−1)/2 steps) is still O(n²). - Phases: consecutive phases cost as much as the slowest one, so O(n) + O(n²) + O(n) = O(n²).
- Several variables: a loop over n rows and m columns is O(nm).
- Recursion: (number of calls) × (cost per call).
f(n)that callsf(n−1)makes n calls, so O(n).g(n)that callsg(n−1)twice makes 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ − 1 calls, so O(2ⁿ).
- Loops: input pe k nested loops = O(nᵏ).
- Order of magnitude: constants aur chhote terms gayab ho jaate hain. 3n, n + 5 ya ⌈n/2⌉ baar chalne wale loops sab O(n) hain, aur pairs
j > iwala loop (n(n−1)/2 steps) bhi O(n²) hi hai. - Phases: ek ke baad ek phases ka cost sabse slow phase jitna — O(n) + O(n²) + O(n) = O(n²).
- Kai variables: n rows aur m columns pe loop = O(nm).
- Recursion: (calls ki ginti) × (har call ka cost).
f(n)jof(n−1)call kare: n calls, O(n).g(n)jog(n−1)ko do baar call kare: 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ − 1 calls, O(2ⁿ).
static long[] sameOrder(int n) { long a = 0, b = 0, c = 0; for (int i = 1; i <= 3 * n; i++) a++; // 3n for (int i = 1; i <= n + 5; i++) b++; // n + 5 for (int i = 1; i <= n; i += 2) c++; // ⌈n/2⌉ return new long[] {a, b, c}; // all O(n)} static long triangle(int n) { long ops = 0; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { ops++; // n(n-1)/2 times → still O(n²) } } return ops;}static long calls; static void f(int n) { // n calls in total → O(n) calls++; if (n == 1) return; f(n - 1);} static void g(int n) { // 1 + 2 + 4 + ... + 2^(n-1) = 2^n - 1 calls → O(2^n) calls++; if (n == 1) return; g(n - 1); g(n - 1);}My notesMere notes
2.2Complexity classes
| Class | Typical cause |
|---|---|
| O(1) | a direct formula |
| O(log n) | halving the input each step (binary search) |
| O(√n) | e.g. trial division up to √n |
| O(n) | one or a few passes over the input |
| O(n log n) | sorting, or n operations on an O(log n) data structure |
| O(n²) | all pairs (two nested loops) |
| O(n³) | all triples |
| O(2ⁿ) | all subsets |
| O(n!) | all permutations |
Everything up to O(nᵏ) is polynomial, which in practice means efficient. For NP-hard problems, no polynomial algorithm is known.
| Class | Aam wajah |
|---|---|
| O(1) | seedha formula |
| O(log n) | har step input aadha (binary search) |
| O(√n) | jaise √n tak trial division |
| O(n) | input pe ek ya kuch passes |
| O(n log n) | sorting, ya O(log n) data structure pe n operations |
| O(n²) | saare pairs (do nested loops) |
| O(n³) | saari triples |
| O(2ⁿ) | saare subsets |
| O(n!) | saare permutations |
O(nᵏ) tak sab polynomial hai — practically efficient. NP-hard problems ke liye koi polynomial algorithm pata nahi hai.
My notesMere notes
2.3Estimating efficiency
A judge does roughly 10⁸ simple operations per second. Plug n into your complexity: with n = 10⁵, O(n²) is 10¹⁰ steps, around 100 seconds, so it is far too slow. The limits also hint at the intended solution:
Judge lagbhag 10⁸ simple operations per second karta hai. Apni complexity mein n daalo: n = 10⁵ pe O(n²) = 10¹⁰ steps ≈ 100 seconds — bahut slow. Limits khud batati hain ki kaunsa solution chahiye:
O(1)1 ops< 1 ms✓O(log n)17 ops< 1 ms✓O(√n)316 ops< 1 ms✓O(n)1.0·10⁵ ops1 ms✓O(n log n)1.7·10⁶ ops17 ms✓O(n²)1.0·10¹⁰ ops100.0 s✗O(n³)1.0·10¹⁵ ops2778 h✗O(2ⁿ)∞ opsforever✗O(n!)∞ opsforever✗Assuming about 10⁸ simple operations per second. ✓ comfortable · ~ borderline (constant factors decide) · ✗ too slow.
| n ≤ 10 | O(n!) | |
| n ≤ 20 | O(2ⁿ) | |
| n ≤ 500 | O(n³) | |
| n ≤ 5,000 | O(n²) | |
| n ≤ 1.0·10⁶ | O(n log n) or O(n) | ← your n |
| n is huge | O(1) or O(log n) |
My notesMere notes
2.4Maximum subarray sum
Problem: find the largest sum of consecutive elements. The empty subarray counts, so the answer is at least 0. In [-1, 2, 4, -3, 5, 2, -5, 2], the best is 2 + 4 − 3 + 5 + 2 = 10.
- O(n³): try every start and end, and add the elements in between.
- O(n²): fix the start and extend the end one step at a time, keeping a running sum, which removes one loop.
- O(n), Kadane: for each position k, keep
sum= the best subarray sum ending at k. That’s eithera[k]alone or the best one ending at k−1 extended bya[k], whichever is larger.
Problem: lagaatar elements ka sabse bada sum. Empty subarray allowed hai, toh answer kam se kam 0. [-1, 2, 4, -3, 5, 2, -5, 2] mein best hai 2 + 4 − 3 + 5 + 2 = 10.
- O(n³): har start aur end try karo, beech ke elements jodo.
- O(n²): start fix karo, end ek-ek step badhao, running sum rakho — ek loop hat gaya.
- O(n), Kadane: har position k ke liye
sum= k pe khatam hone wala best subarray sum. Yeh ya toh akelaa[k]hai, ya k−1 pe khatam hone wala best +a[k]— jo bhi bada ho.
static long quadratic(int[] a) { int n = a.length; long best = 0; for (int x = 0; x < n; x++) { long sum = 0; for (int y = x; y < n; y++) { sum += a[y]; // extend the subarray instead of re-adding it best = Math.max(best, sum); } } return best;}/** Kadane: sum = best subarray sum ending exactly at k. */static long kadane(int[] a) { long best = 0, sum = 0; for (int k = 0; k < a.length; k++) { sum = Math.max(a[k], sum + a[k]); best = Math.max(best, sum); } return best;}- current
- best subarray ending here
- best so far
Idea: for each position k, track sum = the best sum of a subarray that ENDS at k. The answer is the largest such sum (or 0 for the empty subarray).
/** Kadane: sum = best subarray sum ending exactly at k. */static long kadane(int[] a) { long best = 0, sum = 0; for (int k = 0; k < a.length; k++) { sum = Math.max(a[k], sum + a[k]); best = Math.max(best, sum); } return best;}- best
- 0
- sum
- 0
The book’s timings show why the complexity matters more than anything else. At n = 10⁴, the O(n³) version already takes over 10 seconds. At n = 10⁵, the O(n²) one takes 5.3 s. Kadane handles n = 10⁷ instantly.
Book ki timings dikhati hain ki complexity sabse zyada kyun matter karti hai: n = 10⁴ pe O(n³) wala 10 second se zyada leta hai, n = 10⁵ pe O(n²) wala 5.3 s, aur Kadane n = 10⁷ bhi turant kar deta hai.