Beginner's Problem ā Basic Concepts & Complexity Guide
Module 1 ā Basic concepts & the root of programming ā how to think before you code Structured as Topic ā Plain-English Explanation ā Real Code ā Visual Diagram ā Complexity ā Common Pitfalls.
1. What is an Algorithm?
An algorithm is simply a finite, step-by-step set of instructions for solving a problem or completing a task ā nothing more mysterious than a recipe. Just as a recipe takes raw ingredients and turns them into a dish through a defined sequence of steps, an algorithm takes an input and transforms it into the correct output through a defined sequence of operations.
Every algorithm must satisfy a few essential properties:
- Unambiguous: Each step is precisely defined with zero ambiguity for the computer.
- Finite: It terminates after a limited, countable number of steps for every valid input.
- Correctness: It must produce the correct result for every valid input.
- Feasibility: Every operation must be realistically executable with available computational resources.
Programming is the act of translating an algorithm ā usually first sketched in plain English or pseudocode ā into a language a computer can execute.
2. Time & Space Complexity (Big-O Notation)
Two programs can solve the same problem correctly yet perform wildly differently as the input grows.
- Time complexity measures how the number of operations an algorithm performs grows as the input size ($n$) grows.
- Space complexity measures how much extra memory it needs.
Big-O notation is the formal asymptotic language we use to describe this growth, focusing on the worst case and ignoring constant factors ā because what matters for large inputs is the shape of the growth curve, not small constants.
| Notation | Name | Rate of Growth | Example Operation / Algorithm |
|---|---|---|---|
| O(1) | Constant | Flat; unaffected by $n$ | Accessing an array element by index (arr[i]) |
| O(log n) | Logarithmic | Halves search space each step | Binary Search on a sorted array |
| O(n) | Linear | Direct 1:1 scan | Scanning every element once |
| O(n log n) | Linearithmic | Efficient divide-and-conquer | Merge sort, quick sort (average) |
| O(nĀ²) | Quadratic | Squares with $n$ | Bubble sort, nested loops over the same array |
| O(2āæ) | Exponential | Doubles with each added element | Naive recursive Fibonacci, brute-force subsets |
3. Pseudocode & Flowcharts
Pseudocode is a halfway point between plain English and real code: informal, language-agnostic, but structured enough to show exactly what steps happen and in what order. It lets you plan an algorithm's logic before worrying about a specific programming language's syntax.
A flowchart does the same job visually, using standardized shapes:
- Ovals: Start and End delimiters.
- Rectangles: Sequential actions, operations, or assignments.
- Diamonds: Decisions and conditional branching (Yes/No, True/False).
- Arrows: Directed flow of program control.
BEGIN
READ n
IF n < 0 THEN
PRINT "invalid"
ELSE
PRINT "valid, value =", n
END IF
END
- Write pseudocode or sketch a flowchart before coding for any non-trivial problem ā it catches logic errors early, when they're cheap to fix.
- Good pseudocode names variables meaningfully and states loop conditions explicitly, the same discipline you'll want in real code.
4. The Master Theorem for Divide-and-Conquer
Recurrences of the standard divide-and-conquer form $T(n) = a T(n/b) + O(n^d)$ can be solved directly by comparing $log_b a$ against $d$:
- Case 1 ($d < log_b a$): Work at leaves dominates $implies T(n) = Theta(n^{log_b a})$.
- Case 2 ($d = log_b a$): Work is evenly distributed across tree levels $implies T(n) = Theta(n^d log n)$ (e.g. Merge Sort: $a=2, b=2, d=1 implies Theta(n log n)$).
- Case 3 ($d > log_b a$): Work at root dominates $implies T(n) = Theta(n^d)$.
