An algorithm is a step-by-step recipe to solve a problem. Two different recipes can solve the same problem. But one can be much faster. Complexity analysis tells us how fast (time complexity) and how much memory (space complexity) an algorithm needs.

We do not measure time in seconds. Seconds depend on the computer. Instead, we count basic steps (comparisons, additions, assignments) as a function of the input size \( n \). Then we look at how this count grows when \( n \) becomes big.

• Big-O \( O(g(n)) \) — upper bound. The algorithm takes at most about \( g(n) \) steps (for large \( n \)). "It will not be slower than this."
• Big-Omega \( \Omega(g(n)) \) — lower bound. It takes at least about \( g(n) \) steps. "It will not be faster than this."
• Big-Theta \( \Theta(g(n)) \) — tight bound. Both upper and lower bound match. "It takes exactly about \( g(n) \) steps."

Formal (but keep it simple): \( f(n) = O(g(n)) \) means there are constants \( c > 0 \) and \( n_0 \) so that \( f(n) \le c \cdot g(n) \) for all \( n \ge n_0 \). We ignore constant factors and small terms. So \( 3n^2 + 10n + 5 = O(n^2) \).

Rules: nested loops multiply, loops written one after another add. Then keep only the biggest term and drop constants.

For a recursive function, we write a recurrence. Example: merge sort splits the array into 2 halves, solves both, then merges in \( n \) steps:

For recurrences of the form \( T(n) = a\,T(n/b) + n^d \) (with \( a \ge 1, b > 1 \)), compare \( d \) with \( \log_b a \):

• If \( d > \log_b a \): \( T(n) = O(n^d) \) — the outside work wins.
• If \( d = \log_b a \): \( T(n) = O(n^d \log n) \) — both are equal, we get an extra log.
• If \( d < \log_b a \): \( T(n) = O(n^{\log_b a}) \) — the recursive calls win.

Sometimes the exam does not give you the formula. It gives you one data point (how many steps for one input size) and expects you to find the steps for any other size. The trick: if an algorithm is \( \Theta(n^k) \), then steps \( = c \cdot n^k \) for some constant \( c \). The constant cancels when you take a ratio:

Sorting means arranging items in order (small to big, or big to small). It is the most classic algorithm topic. For each sort, learn: how it works, one full trace, and its complexity.

Compare each pair of neighbours. If they are in the wrong order, swap them. After one full pass, the biggest element "bubbles" to the end. Repeat \( n-1 \) passes.

In pass \( i \), find the smallest element in the unsorted part and swap it into position \( i \). It always does about \( n^2/2 \) comparisons, but at most \( n-1 \) swaps (good when swaps are costly).

Like sorting playing cards in your hand. Take the next element and insert it into its correct place inside the already-sorted left part. Very fast (\( O(n) \)) if the array is almost sorted.

Idea: split the array into two halves, sort each half (recursively), then merge the two sorted halves into one sorted array. Merging two sorted lists is easy: repeatedly take the smaller front element.

Idea: pick one element as the pivot. Rearrange (partition) the array so that everything smaller than the pivot goes left, everything bigger goes right. Now the pivot is in its final place. Recursively quick sort the left part and the right part.

If all values are small integers in range 0..k, we can sort without comparing. Count how many times each value appears, then rebuild the array. Time \( O(n + k) \). Example: [4, 2, 2, 8, 3] → counts: 2 appears 2 times, 3 once, 4 once, 8 once → output [2, 2, 3, 4, 8]. It needs extra memory for the count array, and only works for limited integer ranges.

A sort is stable if equal elements keep their original order. Example: sort students by marks; two students both have 80. A stable sort keeps them in their original order. Bubble, insertion, merge, counting sort are stable. Selection and quick sort (typical versions) are not stable.

Check elements one by one from the start until you find the target. Works on any array (sorted or not). Worst case: check all \( n \) elements → \( O(n) \). Average: about \( n/2 \) checks.

Only works on a sorted array. Look at the middle element. If it is the target, done. If the target is smaller, throw away the right half. If bigger, throw away the left half. Every step cuts the search space in half.

Why \( O(\log n) \)? Each step halves the range: \( n \to n/2 \to n/4 \to \dots \to 1 \). If it takes \( k \) steps, then \( n/2^k = 1 \), so \( 2^k = n \), so \( k = \log_2 n \). For n = 1,000,000 only about 20 steps!

Divide and conquer is a 3-step pattern:

1. Divide: break the problem into smaller subproblems of the same type.
2. Conquer: solve each subproblem recursively (tiny ones directly).
3. Combine: join the small answers into the full answer.

You already know two examples: merge sort (divide into halves, sort, merge) and binary search (divide, keep only one half, no combine needed). Quick sort is also divide and conquer (the work happens in the partition, before recursion).

Naive way: multiply \( x \) by itself \( n \) times → \( O(n) \). Divide and conquer way: \( x^n = (x^{n/2})^2 \) if \( n \) is even, and \( x \cdot (x^{(n-1)/2})^2 \) if odd. Only one recursive call!

Split the array in half, find (max, min) of each half recursively, then combine with 2 comparisons: overall max = max of two maxes, overall min = min of two mins. Recurrence: \( T(n) = 2T(n/2) + 2 \). This gives about \( 3n/2 - 2 \) comparisons, better than the naive \( 2n - 2 \) (comparing every element with both current max and min).

A greedy algorithm builds the answer step by step. At every step it takes the choice that looks best right now, and never goes back to change it. Greedy is simple and fast — but it only gives the correct answer for problems with a special structure (the "greedy choice" must be safe). For many problems, greedy is wrong.

Problem: you have activities with start and finish times. One person can do one activity at a time. Pick the maximum number of non-overlapping activities. Greedy rule: sort by finish time, always take the activity that finishes earliest and does not clash with the last taken one.

Problem: make an amount with the fewest coins. Greedy rule: always take the biggest coin that fits.

• Works: coins {25, 10, 5, 1}, amount 63 → 25+25+10+1+1+1 = 6 coins. This is optimal (this coin system is "canonical").
• Fails: coins {1, 3, 4}, amount 6. Greedy: 4+1+1 = 3 coins. Optimal: 3+3 = 2 coins. Greedy got it wrong!

Lesson: greedy needs proof. When greedy fails, we use dynamic programming (next section).

Goal: compress text by giving short binary codes to frequent characters and longer codes to rare ones. Method: make each character a tree node with its frequency. Repeat: take the two nodes with the smallest frequencies, join them under a new parent whose frequency is their sum. Stop when one tree remains. Left edge = 0, right edge = 1. Each character's code = path from root. No code is a prefix of another (prefix-free), so decoding is unambiguous.

Greedy is fast and simple, but it has clear weaknesses. The exam asks you to list the bottlenecks (limitations) of the greedy approach. Learn these five points:

• Local best ≠ global best. Greedy picks what looks best now. A chain of locally best choices can still end at a bad final answer (a local optimum, not the global optimum).
• No lookahead, no backtracking. Greedy never looks at future consequences, and once a choice is made it never goes back to undo it. One early wrong choice can ruin everything.
• Works only for special problems. The problem must have the greedy-choice property (a locally best choice is always safe) and optimal substructure (the best answer contains best answers of subproblems). Most problems do not have both.
• Correctness is hard to prove. Even when greedy is right, proving it (usually by an exchange argument) is tricky. A greedy that "looks right" can silently be wrong.
• Famous failures. Greedy fails on 0/1 knapsack (taking the best ratio item first can miss the optimal) and on coin change with a general coin system (coins {1, 3, 4}, amount 6: greedy gives 3 coins, optimal is 2). These need DP.

DP solves problems that have two properties: overlapping subproblems (the same small problem appears many times) and optimal substructure (the best answer is built from best answers of subproblems). Trick: solve each subproblem once, save the result, reuse it.

• Memoization (top-down): write the normal recursion, but store each result in a table. Before computing, check the table first.
• Tabulation (bottom-up): fill a table from the smallest cases up to the answer, using loops. No recursion.

Naive recursion is \( O(2^n) \) because the same values are computed again and again. DP computes each fib(i) once → \( O(n) \).

Problem: a bag holds weight W. Each item has a weight and a value. Take each item fully or not at all (0/1). Maximize total value. DP: let dp[i][w] = best value using the first \( i \) items with capacity \( w \).

First choice = skip item \( i \). Second choice = take it (only if \( weight_i \le w \)).

A subsequence keeps order but can skip characters. LCS of two strings = the longest subsequence present in both. DP: dp[i][j] = LCS length of first \( i \) chars of X and first \( j \) chars of Y.

dp[v] = minimum coins to make amount \( v \). Base: dp[0] = 0. For each amount, try every coin:

BFS (Breadth-First Search) visits the graph level by level, using a queue. It first sees all neighbours, then neighbours of neighbours. DFS (Depth-First Search) goes as deep as possible along one path, then backtracks, using a stack (or recursion).

For a directed acyclic graph (DAG): order the nodes so every edge goes from earlier to later. Think of courses with prerequisites — take a course only after its prerequisites. Two ways: (1) DFS: after finishing a node, push it on a stack; pop all at the end. (2) Kahn's algorithm: repeatedly remove a node with in-degree 0 (no incoming edges). A cycle makes topological sort impossible. Example: edges 5→2, 5→0, 4→0, 4→1, 2→3, 3→1 → one valid order: 5, 4, 2, 3, 1, 0.

Finds shortest distances from one source to all nodes, when edge weights are non-negative. Greedy idea: keep a distance array. Repeatedly pick the unvisited node with the smallest distance, mark it final, and relax its edges (relax means: if dist[u] + w < dist[v], update dist[v]).

Idea: relax every edge, and repeat this \( V-1 \) times. Any shortest path has at most \( V-1 \) edges, so after \( V-1 \) rounds all distances are correct — even with negative edges. Bonus: run one extra round; if any distance still improves, the graph has a negative cycle (then "shortest path" has no meaning). Complexity: \( O(VE) \) — slower than Dijkstra, but safer.

A spanning tree connects all \( V \) nodes using exactly \( V-1 \) edges, with no cycle. The minimum spanning tree has the smallest total edge weight. Both famous algorithms are greedy:

• Prim: grow one tree. Start from any node; repeatedly add the cheapest edge that connects the tree to a new node.
• Kruskal: sort all edges by weight. Take edges smallest first, but skip any edge that makes a cycle. Stop after \( V-1 \) edges.

DSU (also called Union-Find) keeps track of groups. Two operations: find(x) — which group is x in (follow parents to the root)? union(x, y) — merge two groups. In Kruskal, before taking edge (u, v): if find(u) == find(v) they are already connected, so the edge would make a cycle → skip. Otherwise take the edge and union them. With "path compression" and "union by rank", each operation is almost \( O(1) \). Kruskal total: \( O(E \log E) \) (for sorting).

Imagine a project made of tasks. Each task has a duration, and some tasks must wait for others (dependencies). Tasks with no dependency between them can run in parallel. The whole setup is a DAG (directed acyclic graph): task = node, dependency = edge.

The critical path is the longest path through this DAG (sum of task durations along the path). Key fact: the minimum possible completion time of the whole project = length of the critical path. Why? Every task on that path must run one after another — no parallelism can shorten it. Every other task can fit alongside.

How to find it — forward pass in topological order:

• Earliest Start (ES) of a task = max of Earliest Finish of all its dependencies (0 if none).
• Earliest Finish (EF) = ES + duration.
• Minimum completion time = max EF over all tasks. The critical path is the chain of tasks that produces this max.

Some problems are easy for computers. Some are (probably) very hard. Complexity theory puts problems into classes. BUET has directly asked to define these classes and to draw their relationship diagram. Learn the four names below very well.

P = the set of problems a computer can solve in polynomial time — meaning time like \( O(n) \), \( O(n^2) \), \( O(n^3) \). These are the "easy" (tractable) problems.

• Examples: sorting an array (\( O(n \log n) \)), searching, shortest path with Dijkstra (\( O((V+E)\log V) \)), matrix multiplication.

NP = the set of problems where, if someone gives you a solution, you can verify (check) it in polynomial time. Finding the solution may be hard, but checking is easy.

• Examples: SAT (given a true/false setting of variables, checking the formula is easy), TSP decision version ("is there a tour of length ≤ k?" — given a tour, adding up its length is easy), Sudoku (checking a filled board is easy).
• Every problem in P is also in NP — if you can solve it fast, you can surely check a given answer fast. So \( P \subseteq NP \).

• NP-Complete = the hardest problems inside NP. A problem is NP-Complete if (1) it is in NP, and (2) every problem in NP can be converted (reduced) to it in polynomial time. Solve one NP-Complete problem fast → you solve ALL of NP fast. Examples: SAT (the first one, by Cook's theorem), 3-SAT, TSP decision version, vertex cover, graph coloring, subset sum.
• NP-Hard = at least as hard as every problem in NP, but it does not have to be in NP itself (its answer may not even be checkable fast, or it may not be a yes/no problem). Examples: TSP optimization version ("find the shortest tour" — even checking that a tour is the shortest is hard), the halting problem (not solvable at all!).
• Relationship: NP-Complete = NP ∩ NP-Hard. NP-Complete problems are exactly the NP-Hard problems that also sit inside NP.

Read the diagram like this: P sits inside NP. NP-Hard sticks out to the right — part of it is inside NP, part is outside. The overlap of NP and NP-Hard is exactly NP-Complete. If P = NP were true, the picture would collapse: P, NP and NP-Complete would all become one same set (and NP-Hard would contain that whole set).

Is P = NP? In words: if an answer is easy to check, is it also easy to find? Nobody knows. It is the most famous open problem in computer science, with a $1 million Clay Millennium Prize. Most researchers believe P ≠ NP — that is why we draw the diagram above with P as a strict smaller circle.

NP-Hard problems have no known fast exact algorithm. So in practice we use two kinds of "good enough" methods. BUET asked the difference directly.