Example — Static:

int marks[50];  // fixed size array — always 50 elements
// If only 10 students? 40 slots wasted!
// If 60 students? Cannot accommodate!

🔍 Why This Logic: The size 50 is hardcoded at compile time. The compiler reserves exactly 50 × sizeof(int) bytes on the stack. This memory cannot grow or shrink. If you need more, you must recompile with a larger number — hence “static.”

Example — Dynamic:

struct Node {
    int data;
    struct Node* next;
};
// Create nodes as needed — no waste, no overflow
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

🔍 Why This Logic:

• struct Node — Defines a self-referential structure: each node holds data and a pointer to the next node. This is the building block of linked lists.
• struct Node* next — The pointer that “chains” nodes together. It stores the address of the next node, not the node itself. This allows nodes to be scattered in memory (non-contiguous).
• malloc(sizeof(struct Node)) — Allocates exactly enough bytes for ONE node on the heap at runtime. We can call this repeatedly to add as many nodes as memory allows — hence “dynamic.”

Example — Algorithm to find the maximum of three numbers:

Algorithm: FindMax(a, b, c)
Input: Three numbers a, b, c
Output: The largest of the three

Step 1: Set max = a
Step 2: If b > max, then set max = b
Step 3: If c > max, then set max = c
Step 4: Return max

✅ Finite — exactly 4 steps
✅ Definite — each step is clear
✅ Has input (a, b, c) and output (max)
✅ Effective — only comparisons and assignments

Example — Flowchart logic for finding the largest of two numbers:

[START]
   ↓
[Read a, b]
   ↓
<Is a > b?> ──Yes──→ [Print a]
   │                      ↓
   No                  [STOP]
   ↓
[Print b]
   ↓
[STOP]

Example — Pseudo code for Linear Search:

ALGORITHM LinearSearch(A, n, key)
// Input:  Array A of n elements, search key
// Output: Index of key in A, or -1 if not found

BEGIN
    FOR i = 0 TO n-1 DO
        IF A[i] == key THEN
            RETURN i
        ENDIF
    ENDFOR
    RETURN -1
END

Example — Pseudo code for finding Factorial:

ALGORITHM Factorial(n)
// Input:  Non-negative integer n
// Output: n! (factorial of n)

BEGIN
    SET result = 1
    FOR i = 1 TO n DO
        SET result = result * i
    ENDFOR
    RETURN result
END

Example 1 — Constant space $O(1)$:

int sum(int a, int b) {
    return a + b;  // Only uses fixed variables
}
// Space = O(1) — no extra data structures

🔍 Line-by-Line Logic:

• int sum(int a, int b) — Takes two parameters stored in the function’s stack frame. A fixed number of variables regardless of their values.
• return a + b; — One addition, one return. No arrays, no malloc, no recursion. The only memory used is for a, b, and the return value — all fixed-size.
• Why $O(1)$ space? — Memory consumption does NOT depend on input values. Whether a = 5 or a = 1000000, the same number of variables is used. This is the definition of constant space.

Example 2 — Linear space $O(n)$:

int* copyArray(int arr[], int n) {
    int* copy = (int*)malloc(n * sizeof(int));  // n extra elements
    for (int i = 0; i < n; i++)
        copy[i] = arr[i];
    return copy;
}
// Space = O(n) — creates array of size n

🔍 Line-by-Line Logic:

• int* copyArray(int arr[], int n) — Returns a pointer to a new array. The original arr[] is passed by reference (pointer to first element), so no copy of the input is made here.
• int* copy = (int*)malloc(n * sizeof(int)) — The KEY line. malloc allocates n × sizeof(int) bytes on the heap at runtime. This single line is responsible for the $O(n)$ space. We multiply by sizeof(int) because malloc works in bytes, and (int*) casts the raw void* to an integer pointer.
• for (int i = 0; i < n; i++) copy[i] = arr[i]; — Copies elements one-by-one. The loop variable i is $O(1)$ extra space — it doesn’t change the overall $O(n)$ analysis.
• return copy; — Returns the heap pointer to the caller. The caller must eventually call free(copy) to avoid a memory leak.
• Why $O(n)$ space? — We created a brand-new array of n elements. The extra memory grows linearly with input size.

Example 3 — Recursion space $O(n)$:

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // n function calls on stack
}
// Space = O(n) — recursion depth is n

🔍 Line-by-Line Logic:

• if (n <= 1) return 1; — Base case: $0! = 1$ and $1! = 1$. Without this, the recursion would never stop → stack overflow. Every recursive function MUST have a base case.
• return n * factorial(n - 1); — Recursive case: uses the mathematical definition $n! = n \times (n-1)!$. Each call creates a NEW stack frame containing its own copy of n and a return address.
• Why $O(n)$ space? — When we call factorial(5), the call stack builds up: factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1). At peak, there are 5 stack frames simultaneously alive (none can return until the one it called returns). For input n, that’s n frames → $O(n)$ space.
• Contrast with iterative version: A loop for (int i = 1; i <= n; i++) result *= i; uses $O(1)$ space because it reuses the same variables. The recursive version trades space efficiency for code elegance.

Example: If $T(n) = 3n^2 + 5n + 2$, then $T(n) = O(n^2)$.

Proof: Choose $c = 4$ and $n_0 = 6$:
For $n \geq 6$: $3n^2 + 5n + 2 \leq 3n^2 + n^2 = 4n^2$ ✔

We say the algorithm has “order $n^2$” or “quadratic time.”

Example: If $T(n) = 3n^2 + 5n + 2$, then $T(n) = \Omega(n^2)$.

Proof: Choose $c = 3$ and $n_0 = 1$:
For $n \geq 1$: $3n^2 + 5n + 2 \geq 3n^2$ ✔

Example: $T(n) = 3n^2 + 5n + 2 = \Theta(n^2)$

Because: $T(n) = O(n^2)$ AND $T(n) = \Omega(n^2)$, therefore $T(n) = \Theta(n^2)$.

Example — Linear Search in an array of $n$ elements:

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key)
            return i;
    }
    return -1;
}

🔍 Line-by-Line Logic:

• int linearSearch(int arr[], int n, int key) — Takes the array, its size n, and the target key. We pass n separately because C arrays don’t carry their size.
• for (int i = 0; i < n; i++) — Scans every element from index 0 to n-1. This is the brute-force approach — no assumptions about data ordering.
• if (arr[i] == key) return i; — Early exit: the moment we find the key, we return its index immediately. This is why the best case is $O(1)$ — if the key is at index 0, we check once and leave.
• return -1; — If the loop finishes without finding key, we return -1 (a sentinel value meaning “not found”). This is the worst case — we checked ALL n elements.
• Why linear? — We have no way to skip elements. Unlike binary search (which requires sorted data), linear search works on any array but must potentially examine every element → $O(n)$.

Example — Insertion Sort:

Example 1 — Analyze this code:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        printf("*");
    }
}

🔍 Why This Logic:

• j < i (not j < n) — This is the critical detail. The inner loop runs a variable number of times that depends on the outer loop’s current value of i. When i = 0, inner runs 0 times; when i = 5, inner runs 5 times.
• Why does this produce $\frac{n(n-1)}{2}$? — The total work is $0 + 1 + 2 + … + (n-1)$, which is the triangular number formula. This pattern appears everywhere: bubble sort’s comparisons, selection sort’s comparisons, printing triangle patterns.
• Still $O(n^2)$ — Even though it’s roughly half of $n^2$, constants don’t matter in Big O. $\frac{n^2}{2}$ and $n^2$ are both $O(n^2)$.

Analysis:

• When $i = 0$: inner loop runs 0 times
• When $i = 1$: inner loop runs 1 time
• When $i = 2$: inner loop runs 2 times
• …
• When $i = n-1$: inner loop runs $n-1$ times

Total operations = $0 + 1 + 2 + … + (n-1) = \frac{n(n-1)}{2} = \frac{n^2 - n}{2}$

Example 2 — Analyze this code:

for (int i = 1; i <= n; i *= 2) {
    for (int j = 0; j < n; j++) {
        printf("*");
    }
}

🔍 Why This Logic:

• i *= 2 — The outer loop doubles i each iteration: $1, 2, 4, 8, 16, …$. It reaches n after $\log_2 n$ steps (because $2^k = n \implies k = \log_2 n$). This is the hallmark of logarithmic behavior.
• j < n — The inner loop ALWAYS runs exactly n times, regardless of i. It doesn’t depend on the outer variable (unlike Example 1).
• Why $O(n \log n)$? — The outer loop runs $\log n$ times, the inner runs $n$ times per outer iteration. By the multiplication rule: $\log n \times n = n \log n$. This is the same complexity as merge sort and quick sort (average case).

Analysis:

• Outer loop: $i = 1, 2, 4, 8, …, n$ → runs $\log_2 n$ times
• Inner loop: always runs $n$ times

Total = $n \times \log n$

Example 3 — Analyze this code:

int i = 1, s = 0;
while (s < n) {
    s = s + i;
    i++;
}

🔍 Why This Logic:

• s = s + i; i++; — In each iteration, we add an increasing value to s. First we add 1, then 2, then 3, etc. So after $k$ iterations, $s = 1 + 2 + 3 + … + k = \frac{k(k+1)}{2}$.
• Why $O(\sqrt{n})$? — The loop stops when $s \geq n$, i.e., $\frac{k(k+1)}{2} \geq n$, so $k \approx \sqrt{2n}$. Dropping the constant: $O(\sqrt{n})$. This is between $O(\log n)$ and $O(n)$ in the growth hierarchy.
• Key insight: Any loop where the “progress per step” increases (here: $+1, +2, +3, …$) tends to finish faster than linear. The accumulating sum reaches n in $\sqrt{n}$ steps rather than n steps.

Analysis:

• After $k$ iterations: $s = 1 + 2 + 3 + … + k = \frac{k(k+1)}{2}$
• Loop stops when $s \geq n$, i.e., $\frac{k(k+1)}{2} \geq n$
• So $k^2 \approx 2n$, meaning $k \approx \sqrt{2n}$

Example 4 — Analyze this recursive function:

void fun(int n) {
    if (n <= 0) return;
    printf("%d ", n);
    fun(n - 1);
}

🔍 Why This Logic:

• if (n <= 0) return; — Base case. Stops the recursion when n hits 0. Without this: infinite recursion → stack overflow.
• printf("%d ", n); — $O(1)$ work done before the recursive call. This means it prints in descending order: $n, n-1, …, 1$.
• fun(n - 1); — Tail recursion: the recursive call is the LAST statement. Each call reduces n by exactly 1, so there are exactly n calls before hitting the base case.
• Why $O(n)$? — Each call does $O(1)$ work + makes exactly ONE recursive call with n-1. The recurrence $T(n) = T(n-1) + O(1)$ unrolls to $T(n) = n \cdot O(1) = O(n)$. This is the simplest form of linear recursion.

Analysis:

• Recurrence: $T(n) = T(n-1) + O(1)$, with $T(0) = O(1)$
• Unrolling: $T(n) = T(n-1) + 1 = T(n-2) + 2 = … = T(0) + n = n + 1$

Example 5 — Analyze this recursive function:

void fun(int n) {
    if (n <= 1) return;
    fun(n / 2);
    fun(n / 2);
}

🔍 Why This Logic:

• if (n <= 1) return; — Base case when the problem size is trivially small.
• Two calls to fun(n / 2) — Each call halves the input, and there are two such calls. This creates a binary tree of recursive calls.
• Why $O(n)$ and not $O(\log n)$? — A single call to fun(n/2) would give $O(\log n)$. But with TWO calls, the recursion tree has $1 + 2 + 4 + … + n = 2n - 1$ nodes (a complete binary tree of height $\log n$). The total work across ALL nodes is $O(n)$.
• Master Theorem: $T(n) = 2T(n/2) + O(1)$ falls into Case 1: $a = 2, b = 2$, so $\log_b a = 1 > 0$ (exponent of $f(n) = n^0$). Result: $T(n) = \Theta(n^{\log_b a}) = \Theta(n)$.
• Key lesson: Branching factor matters enormously. One recursive call → $O(\log n)$. Two recursive calls → $O(n)$. Three calls of fun(n/2) would give $O(n^{\log_2 3}) \approx O(n^{1.58})$!

Analysis:

• Recurrence: $T(n) = 2T(n/2) + O(1)$
• By Master theorem (Case 1): $a = 2, b = 2, f(n) = O(1)$
• $\log_b a = \log_2 2 = 1$, and $f(n) = O(n^0)$ where $0 < 1$