TA 1: Induction, Bubble Sort, and Asymptotic Notations

DAST 67109 | Recitation 1

1. Induction - Recap

What is Induction?

A mathematical proof technique used to prove that a property $P(n)$ holds for every natural number $n$ .

Two steps:

Base case: prove the property holds for the first element
Induction step: prove that if the property holds for one natural number, then it holds for the next

Two types of induction:

Weak induction: assume property holds for $k$ , prove for $k+1$
Strong induction: assume property holds for all $m < n$ , prove for $n$

Weak Induction Example

Prove:

\sum_{i=1}^{n} i = \frac{n(n+1)}{2}

Base: For $n = 1$ , clear by computation.

Assumption: Assume the claim holds for $n$ .

Step:

$\sum_{i=1}^{n+1} i = \sum_{i=1}^{n} i + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$

Strong Induction Example

Chocolate Bar Problem

A chocolate bar with $n$ square blocks takes exactly $n-1$ snaps to separate into individual squares, no matter how we split it.

Base: For $n = 1$ , clear.

Assumption: For every $m < n$ , the claim holds.

Step: Snap the bar into two pieces: one with $k$ blocks and one with $n-k$ blocks.

By assumption: first bar needs $k-1$ snaps, second needs $n-k-1$ snaps.

Total: $(k-1) + (n-k-1) + 1 = n - 1$ snaps. $\square$

2. Bubble Sort Algorithm

Problem

Given an array $A$ of $n$ numbers, sort them in ascending order:

$B[0] \leq B[1] \leq \ldots \leq B[n-1]$

Algorithm

Create a pointer $j$ starting at the first element. Do $n-1$ iterations. In each iteration, compare adjacent elements $A[j]$ and $A[j+1]$ ; if $A[j] > A[j+1]$ , swap them. Increment $j$ and continue.

procedure bubbleSort(list: array of items)
    loop = list.size
    for i = 0 to loop-1 do:
        swapped = false
        for j = 0 to loop-1 do:
            if list[j] > list[j+1] then
                swap(list[j], list[j+1])
                swapped = true
            end if
        end for
        if (not swapped) then
            break
        end if
    end for
end procedure
return list

Proof of Correctness

Claim

After iteration $i$ , the sub-array $A[n-1], \ldots, A[n-i]$ contains the $i$ biggest elements in ascending order:

$A[n-i] \leq A[n-i+1] \leq \ldots \leq A[n-1]$

Proof by induction on $i$ :

Base ( $i = 1$ ): Let $a = \max_{0 \leq j \leq n-1} A[j]$ and $k$ be the last index where $a$ appears. Since $A[k]$ is larger than all elements after it, the algorithm swaps $A[k]$ with $A[k+1]$ , then $A[k+1]$ with $A[k+2]$ , and so on until $A[n-1] = a$ .

Step: Assume correct for $i$ . In iteration $i+1$ , the largest remaining element $b = \max_{0 \leq j \leq n-(i+1)} A[j]$ similarly "bubbles up" to position $n-(i+1)$ , extending the sorted suffix.

Time Complexity

Inner loop operations per iteration (worst case):

Comparison: 1 operation
Swap: 3 operations
Assignment: 1 operation
Total: 5 operations = $O(1)$ per pair

Inner loop: $5n$ operations. Outer loop: $n$ iterations with $5n + 1$ operations each.

$\text{Total} = n \cdot (5n + 1) = 5n^2 + n = O(n^2)$

Best case (already sorted): swapped stays false, only one outer iteration, giving $O(n)$ .

Space Complexity

Only two extra variables (loop and swap), each $O(1)$ .

$\text{Space} = O(1) + O(1) = O(1)$

3. Asymptotic Notations - Recap

Definition: Big O

$f(n) = O(g(n))$ if $\exists N \in \mathbb{N}, \exists c > 0$ s.t. $\forall n \geq N$ : $f(n) \leq c \cdot g(n)$

Definition: Big Omega

$f(n) = \Omega(g(n))$ if $\exists N \in \mathbb{N}, \exists b > 0$ s.t. $\forall n \geq N$ : $f(n) \geq b \cdot g(n)$

Definition: Big Theta

$f(n) = \Theta(g(n))$ if $f(n) = \Omega(g(n))$ and $f(n) = O(g(n))$

Definition: Small o

$f(n) = o(g(n))$ if $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$

Definition: Small omega

$f(n) = \omega(g(n))$ if $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$

Important remark: The notations $o, O, \omega, \Omega, \Theta$ represent sets. Writing $f(n) = O(g(n))$ is shorthand for $f(n) \in O(g(n))$ .

Example: Finding an Asymptotic Upper Bound

Given:

$f(1) = 1, \quad \forall n > 1: \; f(n) = 2 \cdot f\!\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + 1$

Since $f$ is monotonic, we can assume $n = 2^k$ .

Unraveling the recursion:

$f(n) = 2f\!\left(\frac{n}{2}\right) + 1 = 4f\!\left(\frac{n}{4}\right) + 3 = 8f\!\left(\frac{n}{8}\right) + 7 = \ldots = 2^k f\!\left(\frac{n}{2^k}\right) + 2^k - 1$

Setting $k = \log_2 n$ :

$f(n) = n \cdot f(1) + n - 1 = 2n - 1$

Claim: $f(n) = O(n)$ .

Bad Proof Attempt

Choose $N = 1, c = 10$ . Try to show $f(n) < cn$ .

Step: $f(n) = 2f\!\left(\lfloor \frac{n}{2} \rfloor\right) + 1 < 2c \cdot \frac{n}{2} + 1 = cn + 1$

Problem: We need $f(n) < cn$ , but got $cn + 1$ !

Good Proof

Choose $N = 1, c = 10$ . Show $f(n) < cn - 1$ .

Base: $f(1) = 1 < 9 = 10 \cdot 1 - 1$ . ✓

Step:

$f(n) = 2f\!\left(\lfloor \frac{n}{2} \rfloor\right) + 1 < 2\!\left(c \cdot \frac{n}{2} - 1\right) + 1 = cn - 2 + 1 = cn - 1$

Correct! $f(n) < cn - 1$ . $\square$

4. L'Hopital's Rule (If time permits)

If $\lim_{x \to c} f(x) = \lim_{x \to c} g(x) = 0$ or $\lim_{x \to c} |f(x)| = \lim_{x \to c} |g(x)| = \infty$ , and $\lim_{x \to c} \frac{f'(x)}{g'(x)} = L$ exists, then:

$\lim_{x \to c} \frac{f(x)}{g(x)} = \lim_{x \to c} \frac{f'(x)}{g'(x)} = L$

TA 1: Induction, Bubble Sort, and Asymptotic Notations

DAST 67109 | Recitation 1

1. Induction - Recap

What is Induction?

A mathematical proof technique used to prove that a property $P(n)$ holds for every natural number $n$ .

Two steps:

Base case: prove the property holds for the first element
Induction step: prove that if the property holds for one natural number, then it holds for the next

Two types of induction:

Weak induction: assume property holds for $k$ , prove for $k+1$
Strong induction: assume property holds for all $m < n$ , prove for $n$

Weak Induction Example

Prove:

\sum_{i=1}^{n} i = \frac{n(n+1)}{2}

Base: For $n = 1$ , clear by computation.

Assumption: Assume the claim holds for $n$ .

Step:

$\sum_{i=1}^{n+1} i = \sum_{i=1}^{n} i + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$

Strong Induction Example

Chocolate Bar Problem

A chocolate bar with $n$ square blocks takes exactly $n-1$ snaps to separate into individual squares, no matter how we split it.

Base: For $n = 1$ , clear.

Assumption: For every $m < n$ , the claim holds.

Step: Snap the bar into two pieces: one with $k$ blocks and one with $n-k$ blocks.

By assumption: first bar needs $k-1$ snaps, second needs $n-k-1$ snaps.

Total: $(k-1) + (n-k-1) + 1 = n - 1$ snaps. $\square$

2. Bubble Sort Algorithm

Problem

Given an array $A$ of $n$ numbers, sort them in ascending order:

$B[0] \leq B[1] \leq \ldots \leq B[n-1]$

Algorithm

Create a pointer $j$ starting at the first element. Do $n-1$ iterations. In each iteration, compare adjacent elements $A[j]$ and $A[j+1]$ ; if $A[j] > A[j+1]$ , swap them. Increment $j$ and continue.

procedure bubbleSort(list: array of items)
    loop = list.size
    for i = 0 to loop-1 do:
        swapped = false
        for j = 0 to loop-1 do:
            if list[j] > list[j+1] then
                swap(list[j], list[j+1])
                swapped = true
            end if
        end for
        if (not swapped) then
            break
        end if
    end for
end procedure
return list

Proof of Correctness

Claim

After iteration $i$ , the sub-array $A[n-1], \ldots, A[n-i]$ contains the $i$ biggest elements in ascending order:

$A[n-i] \leq A[n-i+1] \leq \ldots \leq A[n-1]$

Proof by induction on $i$ :

Time Complexity

Inner loop operations per iteration (worst case):

Comparison: 1 operation
Swap: 3 operations
Assignment: 1 operation
Total: 5 operations = $O(1)$ per pair

Inner loop: $5n$ operations. Outer loop: $n$ iterations with $5n + 1$ operations each.

$\text{Total} = n \cdot (5n + 1) = 5n^2 + n = O(n^2)$

Best case (already sorted): swapped stays false, only one outer iteration, giving $O(n)$ .

Space Complexity

Only two extra variables (loop and swap), each $O(1)$ .

$\text{Space} = O(1) + O(1) = O(1)$

3. Asymptotic Notations - Recap

Definition: Big O

$f(n) = O(g(n))$ if $\exists N \in \mathbb{N}, \exists c > 0$ s.t. $\forall n \geq N$ : $f(n) \leq c \cdot g(n)$

Definition: Big Omega

$f(n) = \Omega(g(n))$ if $\exists N \in \mathbb{N}, \exists b > 0$ s.t. $\forall n \geq N$ : $f(n) \geq b \cdot g(n)$

Definition: Big Theta

$f(n) = \Theta(g(n))$ if $f(n) = \Omega(g(n))$ and $f(n) = O(g(n))$

Definition: Small o

$f(n) = o(g(n))$ if $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$

Definition: Small omega

$f(n) = \omega(g(n))$ if $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$

Important remark: The notations $o, O, \omega, \Omega, \Theta$ represent sets. Writing $f(n) = O(g(n))$ is shorthand for $f(n) \in O(g(n))$ .

Example: Finding an Asymptotic Upper Bound

Given:

$f(1) = 1, \quad \forall n > 1: \; f(n) = 2 \cdot f\!\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + 1$

Since $f$ is monotonic, we can assume $n = 2^k$ .

Unraveling the recursion:

$f(n) = 2f\!\left(\frac{n}{2}\right) + 1 = 4f\!\left(\frac{n}{4}\right) + 3 = 8f\!\left(\frac{n}{8}\right) + 7 = \ldots = 2^k f\!\left(\frac{n}{2^k}\right) + 2^k - 1$

Setting $k = \log_2 n$ :

$f(n) = n \cdot f(1) + n - 1 = 2n - 1$

Claim: $f(n) = O(n)$ .

Bad Proof Attempt

Choose $N = 1, c = 10$ . Try to show $f(n) < cn$ .

Step: $f(n) = 2f\!\left(\lfloor \frac{n}{2} \rfloor\right) + 1 < 2c \cdot \frac{n}{2} + 1 = cn + 1$

Problem: We need $f(n) < cn$ , but got $cn + 1$ !

Good Proof

Choose $N = 1, c = 10$ . Show $f(n) < cn - 1$ .

Base: $f(1) = 1 < 9 = 10 \cdot 1 - 1$ . ✓

Step:

$f(n) = 2f\!\left(\lfloor \frac{n}{2} \rfloor\right) + 1 < 2\!\left(c \cdot \frac{n}{2} - 1\right) + 1 = cn - 2 + 1 = cn - 1$

Correct! $f(n) < cn - 1$ . $\square$

4. L'Hopital's Rule (If time permits)

If $\lim_{x \to c} f(x) = \lim_{x \to c} g(x) = 0$ or $\lim_{x \to c} |f(x)| = \lim_{x \to c} |g(x)| = \infty$ , and $\lim_{x \to c} \frac{f'(x)}{g'(x)} = L$ exists, then:

$\lim_{x \to c} \frac{f(x)}{g(x)} = \lim_{x \to c} \frac{f'(x)}{g'(x)} = L$