PadhaikoAll subjects

Iterative and Numeric Algorithms

Analysis of Algorithms (ENCT 388)

Open in the Padhaiko app

2.1 Algorithm for GCD and Fibonacci number

Iterative algorithms use explicit loops and constant or linear state rather than deep recursion, often reducing both asymptotic time and auxiliary stack space.

Greatest Common Divisor (GCD)

Definition

Iterative GCD (Division Method)

For two non-negative integers (not both zero), is the largest positive integer dividing both and . Using the Euclidean division identity with base case :

Iterative Euclidean GCDC
int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Fibonacci Numbers: Iterative vs. Naive Recursive

The Fibonacci sequence is defined by , , and for .

AspectIterative FibonacciNaive Recursive Fibonacci
MethodMaintain two variables prev and curr and loop Recursively call fib(n-1) + fib(n-2)
Time Complexity additions where (exponential!)
Space Complexity auxiliary space call-stack space
Cause of OverheadNone; each computed onceRecomputes overlapping subproblems exponentially many times
Iterative Fibonacci FunctionC
long long fib_iter(int n) {
    if (n <= 1) return n;
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

2.2 Sequential search

Sequential search (linear search) inspects elements of an unsorted array one by one from left to right until the target key is found or the array ends.

Sequential SearchC
int sequentialSearch(int A[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (A[i] == key) {
            return i;   // found at index i
        }
    }
    return -1;          // not found
}

2.3 Review of bubble sort, selection sort, and insertion sort algorithms

All three classical elementary sorting algorithms sort an array in-place ( extra space) using worst-case comparisons, yet they differ sharply in best-case behavior, swaps, and stability.

Bubble Sort, Selection Sort, and Insertion SortC
void bubbleSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (A[j] > A[j + 1]) {
                int tmp = A[j]; A[j] = A[j + 1]; A[j + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break; // early exit on already-sorted input
    }
}

void selectionSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[minIdx]) minIdx = j;
        }
        int tmp = A[i]; A[i] = A[minIdx]; A[minIdx] = tmp;
    }
}

void insertionSort(int A[], int n) {
    for (int i = 1; i < n; i++) {
        int key = A[i], j = i - 1;
        while (j >= 0 && A[j] > key) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = key;
    }
}
Comparison of Elementary Iterative Sorting Algorithms
AlgorithmBest Case TimeAverage / Worst TimeWorst Swaps / WritesSpaceStableAdaptive
Bubble Sort (with early-exit flag) swapsYesYes
Selection Sort swaps ()NoNo
Insertion Sort shiftsYesYes
Example 1

1 (6 marks)

  1. Trace Insertion Sort on pass by pass, and count the exact number of element shifts (and key comparisons) performed.
  2. How many total function calls does the naive recursive Fibonacci algorithm make to compute (with base cases ), compared to the loop iterations of fib_iter(6)?

Insertion Sort trace on :

  • Pass (key = 10): Compare (shift right) . ( comparison, shift)
  • Pass (key = 14): Compare (shift ), then (false) . ( comparisons, shift)
  • Pass (key = 37): Compare (false) . ( comparison, shifts)
  • Pass (key = 13): Compare (all , shift all ), then (false) . ( comparisons, shifts)

Total element shifts , and total key comparisons .

Counting recursive calls for : Let be the number of calls made by fib(n): , and :

  • recursive calls (note ).

By contrast, fib_iter(6) runs the for loop for — just iterations ().

Answer:
  1. Sorted array: with element shifts and comparisons.
  2. Naive recursive fib(6) makes function calls, whereas fib_iter(6) executes loop iterations to return .

2.4 Number theoretic notations

Number-theoretic algorithms operate on integers and modular rings .

Definition

Core Number-Theoretic Notations and Theorems

For a prime , .


2.5 Euclid's and Extended Euclid's algorithms

Euclid's Algorithm

Theorem

Euclid's GCD Recursion Theorem & Lamé's Bound

For any integers and :

Lamé's Theorem (Running Time): If Euclid's algorithm takes division steps on with , then and . Consequently, the number of divisions is (at most times the number of decimal digits of ).

Extended Euclidean Algorithm

The Extended Euclidean Algorithm computes not only , but also integer Bézout coefficients satisfying:

Extended Euclidean AlgorithmC
int extendedGcd(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int x1, y1;
    int d = extendedGcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return d;
}

Finding Modular Inverses: If , then , so is the unique multiplicative inverse .

Example 2

2 (7 marks)

  1. Use the Extended Euclidean Algorithm to find and integers such that .
  2. Find the multiplicative inverse , and solve the modular linear equation .

Extended Euclid on : Forward divisions:

  • .

Back-substitution (or recursive unwinding ):

  • .

Check: .

Modular inverse and solving :

  • For : , , . Thus , so .
  • For : . Since , there are distinct solutions modulo . Dividing by gives . Since , . Thus:

The solutions modulo are and .

Answer:
  1. with ().
  2. ; has solutions: .

2.6 Solving modular linear equations using Chinese remainder theorem

Theorem

Chinese Remainder Theorem (CRT)

Let be pairwise relatively prime positive integers ( for ), and let . Then the system of congruences:

has a unique solution modulo , given explicitly by:

where and (computed via the Extended Euclidean Algorithm).

When solving a single modular linear equation where factors into pairwise coprime moduli, we can split it into smaller congruences , solve each modulo , and recombine with CRT.


2.7 Fermat's theorem

Theorem

Fermat's Little Theorem

If is a prime number, then for every integer not divisible by ():

Equivalently, for every integer (whether or ):

Applications:

  1. Fast Modular Exponentiation (MODULAR-EXPONENTIATION): Using repeated squaring on the binary expansion of exponent , takes modular multiplications, and Fermat's theorem reduces large exponents modulo when is prime.
  2. Fermat Primality Test (and Carmichael Numbers): If for some , then is definitely composite ( is a Fermat witness). However, the converse fails: composite numbers that satisfy for all coprime to are called Carmichael numbers (smallest: ).

2.8 Miller-Rabin randomized primality test and algorithm

The Miller-Rabin primality test overcomes Carmichael numbers by exploiting a stronger property of primes: modulo a prime , the equation has only two square roots, namely and (no nontrivial square roots of unity).

Definition

Miller-Rabin Witness Decomposition

Write an odd integer as:

For a randomly chosen base , compute , then square repeatedly for :

Miller-Rabin Randomized Primality Test (Pseudocode in C Style)C
// Returns 1 if a is a definite witness that n is composite, 0 if n passes
int witness(long long a, long long n) {
    long long d = n - 1;
    int s = 0;
    while (d % 2 == 0) { d /= 2; s++; }
    long long x = modPow(a, d, n);    // a^d mod n via repeated squaring
    if (x == 1 || x == n - 1) return 0;
    for (int r = 1; r < s; r++) {
        x = (x * x) % n;
        if (x == n - 1) return 0;
        if (x == 1) return 1;         // nontrivial square root of 1 found
    }
    return 1;                         // composite
}

// Runs k independent random trials; error probability <= (1/4)^k
int millerRabin(long long n, int k) {
    if (n < 2) return 0;
    if (n == 2 || n == 3) return 1;
    if (n % 2 == 0) return 0;
    for (int i = 0; i < k; i++) {
        long long a = 2 + rand() % (n - 3);
        if (witness(a, n)) return 0;  // definitely composite
    }
    return 1;                         // probably prime
}
Example 3

3 (8 marks)

  1. Solve the simultaneous congruences using the Chinese Remainder Theorem:
  1. Apply the Miller-Rabin witness test to the Carmichael number with base , and show explicitly how it detects compositeness even though .

Chinese Remainder Theorem solution: Here ; ; (pairwise coprime), so .

  • : .
  • : .
  • : .

Combine:

Check: , , .

Miller-Rabin test on with : Factor , so and .

  1. Compute : since , .
  2. Square repeatedly ():

Since appeared immediately after , is a nontrivial square root of ! Thus proves is composite (even though ).

Answer:
  1. Unique CRT solution: .
  2. For () and , the squaring sequence is , revealing the nontrivial square root of and proving is composite.

Exercises

Exercises — Iterative and Numeric Algorithms

Question 1

Write iterative and recursive algorithms to compute the -th Fibonacci number (). Compare their time and space complexities, and determine the exact number of recursive calls needed to compute .

Iterative vs. recursive algorithms and complexity:

  • Iterative: Loops updating prev, curr in time and space.
  • Naive Recursive: Calls fib(n-1) + fib(n-2), yielding recurrence time and call-stack space.

Exact call count for : Using and : , , , and calls (returning ).

Answer:

Iterative Fibonacci takes time and space; naive recursive Fibonacci takes time and space, making recursive calls to compute .

Question 2

Compare Bubble Sort, Selection Sort, and Insertion Sort on the array by counting the exact number of element swaps performed by Selection Sort vs. element swaps performed by standard Bubble Sort (without early exit, and with early exit). Which of the three is both stable and adaptive?

Selection Sort swaps on ():

  • : min in is (idx 1), swap ( swap)
  • : min in is (idx 3), swap ( swap)
  • : min in is (idx 2), swap with self or skip ( effective swaps; unconditional swap gives swaps)
  • : min in is (idx 3), already in place.

Total effective swaps (at most swaps total), while comparisons are always .

Bubble Sort swaps on :

  • Pass 1 (): swap ; swap ; swap ; no swap. ( swaps)
  • Pass 2 (): ok; swap ; ok. ( swap)
  • Pass 3 (): , ok early exit triggers here ( swaps); without early exit, Pass 4 also runs with swaps.

Total swaps (equal to the inversion count of ). Both Bubble Sort (with early exit) and Insertion Sort are stable and adaptive; Selection Sort is neither.

Answer:

Selection Sort performs comparisons and effective swaps (at most ); Bubble Sort performs swaps (terminating after Pass 3 with early exit). Bubble Sort (with early exit) and Insertion Sort are both stable and adaptive.

Question 3
  1. Apply the Extended Euclidean Algorithm to find and integers satisfying .
  2. Find the multiplicative inverse of modulo .

Extended Euclid on :

  • .

Back-substituting:

So .

Multiplicative inverse :

  • .

Thus , so .

Answer:
  1. with .
  2. .
Question 4

Using the Chinese Remainder Theorem, find the smallest positive integer satisfying the system of congruences:

Computing , , and inverses : Moduli are pairwise coprime, so :

  • : .
  • : .
  • : .

Combining into the unique solution modulo :

Reducing modulo : .

Answer:

The smallest positive solution is (unique modulo ).

Question 5
  1. Use Fermat's Little Theorem to compute .
  2. Explain what a Carmichael number is (using ) and why the Miller-Rabin randomized primality test detects composite numbers that fool the simple Fermat test, stating the error probability after independent trials.

Evaluating : Since is prime and , Fermat's Little Theorem gives . Since :

Carmichael numbers vs. Miller-Rabin: A Carmichael number is a composite integer (e.g. ) that satisfies for every coprime to , causing the simple Fermat test to misclassify it as prime for almost all bases. Miller-Rabin decomposes and inspects the squaring chain : any nontrivial square root of (an whose square is ) proves is composite. For any odd composite , at most of bases lie; after independent trials, the false-prime error probability is at most .

Answer:
  1. .
  2. Carmichael numbers pass for all coprime , defeating the Fermat test; Miller-Rabin catches them by detecting nontrivial square roots of , achieving error probability after random trials.
← Introduction to Algorithm AnalysisDivide and Conquer Algorithms →