Algorithm Fundamentals: Complexity Analysis, Big-O Notation, Search & Sorting Algorithms

This guide is a comprehensive introduction to algorithm fundamentals – covering complexity analysis, Big-O notation, search algorithms, and sorting algorithms with practical examples.

In a Nutshell

Algorithms are step-by-step instructions for solving problems. Big-O notation describes their complexity, search algorithms find elements, and sorting algorithms organize data.

Technical Overview

Algorithms are well-defined, finite sequences of instructions that solve a problem. They form the foundation of computer science and software development.

Complexity Analysis:

• Time Complexity: The number of operations as a function of input size
• Space Complexity: The memory required
• Big-O Notation: Upper bound of complexity
• Best/Average/Worst Case: Different runtime scenarios

Big-O Notation (most common):

• O(1): Constant time
• O(log n): Logarithmic time
• O(n): Linear time
• O(n log n): Linearithmic time
• O(n²): Quadratic time
• O(2ⁿ): Exponential time

Key Exam Topics

• Algorithms: Well-defined instruction sequences for problem solving
• Big-O Notation: Mathematical description of complexity
• Time Complexity: Number of operations dependent on input size
• Search Algorithms: Linear Search (O(n)), Binary Search (O(log n))
• Sorting Algorithms: Bubble Sort (O(n²)), Quick Sort (O(n log n))
• Best/Worst/Average Case: Different runtime scenarios
• Industry Relevance: Foundation for efficient software development

Core Components

1. Algorithm Concept: Input, processing, output
2. Complexity Analysis: Time and space requirements
3. Big-O Notation: Asymptotic analysis
4. Search Algorithms: Linear and binary search
5. Sorting Algorithms: Various sorting strategies
6. Data Structures: Arrays, lists, trees, graphs
7. Recursion: Self-calling algorithms
8. Divide and Conquer: Problem-solving through decomposition

Practical Examples

1. Big-O Notation and Complexity Analysis

import java.util.*;

public class ComplexityAnalysis {
    
    // O(1) - Constant time
    public int getFirstElement(int[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException("Array is empty");
        }
        return array[0];  // Always one operation
    }
    
    // O(n) - Linear time
    public int findMax(int[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException("Array is empty");
        }
        
        int max = array[0];
        for (int i = 1; i < array.length; i++) {  // n operations
            if (array[i] > max) {
                max = array[i];
            }
        }
        return max;
    }
    
    // O(n²) - Quadratic time
    public void printPairs(int[] array) {
        for (int i = 0; i < array.length; i++) {        // n loops
            for (int j = 0; j < array.length; j++) {    // n loops
                System.out.println(array[i] + ", " + array[j]);
            }
        }
        // Total: n * n = n² operations
    }
    
    // O(log n) - Logarithmic time
    public int powerOfTwo(int n) {
        int result = 1;
        while (n > 0) {  // log₂(n) loop iterations
            result *= 2;
            n /= 2;
        }
        return result;
    }
    
    // O(n log n) - Linearithmic time
    public void mergeSort(int[] array) {
        if (array.length <= 1) {
            return;
        }
        
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        
        mergeSort(left);    // O(log n) recursion depth
        mergeSort(right);
        
        merge(array, left, right);  // O(n) per merge
    }
    
    private void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) {
            result[k++] = left[i++];
        }
        
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }
    
    // O(2ⁿ) - Exponential time
    public int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);  // 2ⁿ calls
    }
    
    // Complexity analysis with timing
    public void analyzeComplexity() {
        int[] sizes = {100, 1000, 10000, 100000};
        
        System.out.println("=== Complexity Analysis ===");
        System.out.println("Size\tO(1)\tO(n)\tO(n²)\tO(log n)");
        
        for (int size : sizes) {
            int[] array = new int[size];
            
            // Fill array with random numbers
            Random random = new Random();
            for (int i = 0; i < size; i++) {
                array[i] = random.nextInt(1000);
            }
            
            // Measure O(1)
            long start = System.nanoTime();
            getFirstElement(array);
            long o1Time = System.nanoTime() - start;
            
            // Measure O(n)
            start = System.nanoTime();
            findMax(array);
            long onTime = System.nanoTime() - start;
            
            // Measure O(n²) (only for small arrays)
            long on2Time = 0;
            if (size <= 1000) {
                start = System.nanoTime();
                printPairs(array);
                on2Time = System.nanoTime() - start;
            }
            
            // Measure O(log n)
            start = System.nanoTime();
            powerOfTwo(size);
            double olognTime = System.nanoTime() - start;
            
            System.out.printf("%d\t%d\t%d\t%d\t%.0f%n",
                             size, o1Time, onTime, on2Time, olognTime);
        }
    }
    
    public static void main(String[] args) {
        ComplexityAnalysis analysis = new ComplexityAnalysis();
        
        // Complexity analysis
        analysis.analyzeComplexity();
        
        // Big-O demonstration
        System.out.println("\n=== Big-O Demonstration ===");
        demonstrateBigO();
        
        // Recursion vs iteration
        System.out.println("\n=== Recursion vs Iteration ===");
        compareRecursionIteration();
    }
    
    private static void demonstrateBigO() {
        int n = 1000;
        ComplexityAnalysis demo = new ComplexityAnalysis();
        
        System.out.println("Demonstration with n = " + n);
        
        // O(1) example
        int[] array = {1, 2, 3, 4, 5};
        System.out.println("O(1) - First element: " + demo.getFirstElement(array));
        
        // O(n) example
        int[] largeArray = new int[n];
        for (int i = 0; i < n; i++) {
            largeArray[i] = i;
        }
        System.out.println("O(n) - Maximum: " + demo.findMax(largeArray));
        
        // O(log n) example
        System.out.println("O(log n) - 2^" + n + " = " + demo.powerOfTwo(n));
        
        // O(n log n) example
        int[] sortArray = new int[100];
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            sortArray[i] = random.nextInt(1000);
        }
        System.out.println("O(n log n) - Merge sort executed");
        demo.mergeSort(sortArray);
        
        // O(n²) example (small array)
        int[] smallArray = {1, 2, 3, 4, 5};
        System.out.println("O(n²) - All pairs:");
        demo.printPairs(smallArray);
    }
    
    private static void compareRecursionIteration() {
        ComplexityAnalysis demo = new ComplexityAnalysis();
        int n = 30;
        
        System.out.println("Fibonacci n = " + n);
        
        // Recursive version (exponential)
        long start = System.nanoTime();
        int recursiveResult = demo.fibonacci(n);
        long recursiveTime = System.nanoTime() - start;
        
        // Iterative version (linear)
        start = System.nanoTime();
        int iterativeResult = fibonacciIterative(n);
        long iterativeTime = System.nanoTime() - start;
        
        System.out.println("Recursive: " + recursiveResult + " (" + recursiveTime + "ns)");
        System.out.println("Iterative: " + iterativeResult + " (" + iterativeTime + "ns)");
        System.out.println("Speedup: " + (recursiveTime / iterativeTime) + "x");
    }
    
    private static int fibonacciIterative(int n) {
        if (n <= 1) return n;
        
        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }
}

2. Search Algorithms

import java.util.*;

public class SearchAlgorithms {
    
    // Linear Search - O(n)
    public static int linearSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i;  // Element found
            }
        }
        return -1;  // Element not found
    }
    
    // Binary Search - O(log n) - Array must be sorted
    public static int binarySearch(int[] sortedArray, int target) {
        int left = 0;
        int right = sortedArray.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (sortedArray[mid] == target) {
                return mid;  // Element found
            } else if (sortedArray[mid] < target) {
                left = mid + 1;  // Search right
            } else {
                right = mid - 1;  // Search left
            }
        }
        
        return -1;  // Element not found
    }
    
    // Interpolation Search - O(log log n) on average
    // Works only for uniformly distributed, sorted arrays
    public static int interpolationSearch(int[] sortedArray, int target) {
        int left = 0;
        int right = sortedArray.length - 1;
        
        while (left <= right && target >= sortedArray[left] && target <= sortedArray[right]) {
            if (left == right) {
                return sortedArray[left] == target ? left : -1;
            }
            
            // Interpolation formula
            int pos = left + ((target - sortedArray[left]) * (right - left)) / 
                        (sortedArray[right] - sortedArray[left]);
            
            if (sortedArray[pos] == target) {
                return pos;
            } else if (sortedArray[pos] < target) {
                left = pos + 1;
            } else {
                right = pos - 1;
            }
        }
        
        return -1;
    }
    
    // Exponential Search - O(log n) for infinitely large arrays
    public static int exponentialSearch(int[] sortedArray, int target) {
        int n = sortedArray.length;
        
        if (sortedArray[0] == target) {
            return 0;
        }
        
        // Find the range where the element might be
        int i = 1;
        while (i < n && sortedArray[i] <= target) {
            i = i * 2;
        }
        
        // Binary search within the found range
        return binarySearchRange(sortedArray, i / 2, Math.min(i, n - 1), target);
    }
    
    private static int binarySearchRange(int[] array, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
    
    // Jump Search - O(√n) for sorted arrays
    public static int jumpSearch(int[] sortedArray, int target) {
        int n = sortedArray.length;
        int step = (int) Math.sqrt(n);
        int prev = 0;
        
        // Find the block where the element might be
        while (sortedArray[Math.min(step, n) - 1] < target) {
            prev = step;
            step += (int) Math.sqrt(n);
            if (prev >= n) {
                return -1;
            }
        }
        
        // Linear search within the block
        while (sortedArray[prev] < target) {
            prev++;
            if (prev == Math.min(step, n)) {
                return -1;
            }
        }
        
        if (sortedArray[prev] == target) {
            return prev;
        }
        
        return -1;
    }
    
    // Performance comparison of search algorithms
    public static void compareSearchAlgorithms() {
        Random random = new Random();
        int[] sizes = {1000, 10000, 100000, 1000000};
        
        System.out.println("=== Search Algorithms Performance Comparison ===");
        System.out.println("Size\tLinear\tBinary\tInterpolation\tJump\tExponential");
        
        for (int size : sizes) {
            int[] array = new int[size];
            
            // Create sorted array
            for (int i = 0; i < size; i++) {
                array[i] = i;
            }
            
            // Select random target
            int target = random.nextInt(size);
            
            // Linear search
            long start = System.nanoTime();
            int linearResult = linearSearch(array, target);
            long linearTime = System.nanoTime() - start;
            
            // Binary search
            start = System.nanoTime();
            int binaryResult = binarySearch(array, target);
            long binaryTime = System.nanoTime() - start;
            
            // Interpolation search
            start = System.nanoTime();
            int interpolationResult = interpolationSearch(array, target);
            long interpolationTime = System.nanoTime() - start;
            
            // Jump search
            start = System.nanoTime();
            int jumpResult = jumpSearch(array, target);
            long jumpTime = System.nanoTime() - start;
            
            // Exponential search
            start = System.nanoTime();
            int exponentialResult = exponentialSearch(array, target);
            long exponentialTime = System.nanoTime() - start;
            
            System.out.printf("%d\t%d\t%d\t%d\t\t%d\t%d%n",
                             size, linearTime, binaryTime, interpolationTime, jumpTime, exponentialTime);
            
            // Verify results
            assert linearResult == target;
            assert binaryResult == target;
            assert interpolationResult == target;
            assert jumpResult == target;
            assert exponentialResult == target;
        }
    }
    
    public static void main(String[] args) {
        // Create test arrays
        int[] unsortedArray = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
        int[] sortedArray = {11, 12, 22, 25, 34, 42, 50, 64, 76, 88, 90};
        
        System.out.println("=== Search Algorithms Demo ===");
        
        // Linear search
        int target = 25;
        int index = linearSearch(unsortedArray, target);
        System.out.println("Linear Search: " + target + " found at index " + index);
        
        // Binary search
        index = binarySearch(sortedArray, target);
        System.out.println("Binary Search: " + target + " found at index " + index);
        
        // Interpolation search
        index = interpolationSearch(sortedArray, 76);
        System.out.println("Interpolation Search: 76 found at index " + index);
        
        // Jump search
        index = jumpSearch(sortedArray, 42);
        System.out.println("Jump Search: 42 found at index " + index);
        
        // Exponential search
        index = exponentialSearch(sortedArray, 88);
        System.out.println("Exponential Search: 88 found at index " + index);
        
        // Performance comparison
        compareSearchAlgorithms();
        
        // Search algorithm properties
        printSearchAlgorithmProperties();
    }
    
    private static void printSearchAlgorithmProperties() {
        System.out.println("\n=== Search Algorithm Properties ===");
        
        String[][] algorithms = {
            {"Linear Search", "O(n)", "Unsorted", "Simple"},
            {"Binary Search", "O(log n)", "Sorted", "Efficient"},
            {"Interpolation Search", "O(log log n)", "Sorted, uniformly distributed", "Very efficient"},
            {"Jump Search", "O(√n)", "Sorted", "Good for large arrays"},
            {"Exponential Search", "O(log n)", "Sorted", "Infinite arrays"}
        };
        
        System.out.println("Algorithm\t\tTime Complexity\tRequirement\t\tDescription");
        System.out.println("---------\t\t--------------\t-----------\t\t-----------");
        
        for (String[] algo : algorithms) {
            System.out.printf("%-20s\t%-15s\t%-20s\t%s%n", algo[0], algo[1], algo[2], algo[3]);
        }
    }
}

3. Sorting Algorithms

import java.util.*;

public class Sortieralgorithmen {
    
    // Bubble Sort - O(n²)
    public static void bubbleSort(int[] array) {
        int n = array.length;
        boolean swapped;
        
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    // Swap elements
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }
            
            // If no swaps occurred, the array is sorted
            if (!swapped) {
                break;
            }
        }
    }
    
    // Selection Sort - O(n²)
    public static void selectionSort(int[] array) {
        int n = array.length;
        
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            
            // Find minimum in unsorted portion
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            
            // Swap minimum with current element
            if (minIndex != i) {
                int temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }
    
    // Insertion Sort - O(n²) worst case, O(n) best case
    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;
            
            // Shift elements until correct position is found
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            
            array[j + 1] = key;
        }
    }
    
    // Quick Sort - O(n log n) average, O(n²) worst case
    public static void quickSort(int[] array) {
        quickSortRecursive(array, 0, array.length - 1);
    }
    
    private static void quickSortRecursive(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            
            quickSortRecursive(array, low, pivotIndex - 1);
            quickSortRecursive(array, pivotIndex + 1, high);
        }
    }
    
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];  // Use last element as pivot
        int i = (low - 1);  // Index of smaller element
        
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                swap(array, i, j);
            }
        }
        
        swap(array, i + 1, high);
        return i + 1;
    }
    
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    // Merge Sort - O(n log n)
    public static void mergeSort(int[] array) {
        if (array.length <= 1) {
            return;
        }
        
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        
        mergeSort(left);
        mergeSort(right);
        
        merge(array, left, right);
    }
    
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) {
            result[k++] = left[i++];
        }
        
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }
    
    // Heap Sort - O(n log n)
    public static void heapSort(int[] array) {
        int n = array.length;
        
        // Build max-heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
        
        // Extract elements from heap
        for (int i = n - 1; i > 0; i--) {
            swap(array, 0, i);
            heapify(array, i, 0);
        }
    }
    
    private static void heapify(int[] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }
        
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }
        
        if (largest != i) {
            swap(array, i, largest);
            heapify(array, n, largest);
        }
    }
    
    // Performance comparison of sorting algorithms
    public static void compareSortingAlgorithms() {
        Random random = new Random();
        int[] sizes = {1000, 5000, 10000, 20000};
        
        System.out.println("=== Sorting Algorithms Performance Comparison ===");
        System.out.println("Size\tBubble\tSelection\tInsertion\tQuick\tMerge\tHeap");
        
        for (int size : sizes) {
            // Create test array
            int[] originalArray = new int[size];
            for (int i = 0; i < size; i++) {
                originalArray[i] = random.nextInt(10000);
            }
            
            long[] times = new long[6];
            String[] names = {"Bubble", "Selection", "Insertion", "Quick", "Merge", "Heap"};
            
            // Bubble Sort
            int[] array = originalArray.clone();
            long start = System.nanoTime();
            bubbleSort(array);
            times[0] = System.nanoTime() - start;
            
            // Selection Sort
            array = originalArray.clone();
            start = System.nanoTime();
            selectionSort(array);
            times[1] = System.nanoTime() - start;
            
            // Insertion Sort
            array = originalArray.clone();
            start = System.nanoTime();
            insertionSort(array);
            times[2] = System.nanoTime() - start;
            
            // Quick Sort
            array = originalArray.clone();
            start = System.nanoTime();
            quickSort(array);
            times[3] = System.nanoTime() - start;
            
            // Merge Sort
            array = originalArray.clone();
            start = System.nanoTime();
            mergeSort(array);
            times[4] = System.nanoTime() - start;
            
            // Heap Sort
            array = originalArray.clone();
            start = System.nanoTime();
            heapSort(array);
            times[5] = System.nanoTime() - start;
            
            // Print results
            System.out.printf("%d", size);
            for (long time : times) {
                System.out.printf("\t%d", time);
            }
            System.out.println();
        }
    }
    
    // Stability test
    public static void testStability() {
        System.out.println("\n=== Stability Test ===");
        
        // Array with duplicates
        int[] array = {5, 2, 8, 5, 1, 9, 3, 5};
        
        System.out.println("Original: " + Arrays.toString(array));
        
        // Bubble Sort (stable)
        int[] bubbleArray = array.clone();
        bubbleSort(bubbleArray);
        System.out.println("Bubble Sort: " + Arrays.toString(bubbleArray));
        
        // Quick Sort (unstable)
        int[] quickArray = array.clone();
        quickSort(quickArray);
        System.out.println("Quick Sort: " + Arrays.toString(quickArray));
        
        // Merge Sort (stable)
        int[] mergeArray = array.clone();
        mergeSort(mergeArray);
        System.out.println("Merge Sort: " + Arrays.toString(mergeArray));
    }
    
    public static void main(String[] args) {
        // Test array
        int[] array = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
        
        System.out.println("=== Sorting Algorithms Demo ===");
        
        // Bubble Sort
        int[] bubbleArray = array.clone();
        bubbleSort(bubbleArray);
        System.out.println("Bubble Sort: " + Arrays.toString(bubbleArray));
        
        // Selection Sort
        int[] selectionArray = array.clone();
        selectionSort(selectionArray);
        System.out.println("Selection Sort: " + Arrays.toString(selectionArray));
        
        // Insertion Sort
        int[] insertionArray = array.clone();
        insertionSort(insertionArray);
        System.out.println("Insertion Sort: " + Arrays.toString(insertionArray));
        
        // Quick Sort
        int[] quickArray = array.clone();
        quickSort(quickArray);
        System.out.println("Quick Sort: " + Arrays.toString(quickArray));
        
        // Merge Sort
        int[] mergeArray = array.clone();
        mergeSort(mergeArray);
        System.out.println("Merge Sort: " + Arrays.toString(mergeArray));
        
        // Heap Sort
        int[] heapArray = array.clone();
        heapSort(heapArray);
        System.out.println("Heap Sort: " + Arrays.toString(heapArray));
        
        // Performance comparison
        compareSortingAlgorithms();
        
        // Stability test
        testStability();
        
        // Sorting algorithm properties
        printSortingAlgorithmProperties();
    }
    
    private static void printSortingAlgorithmProperties() {
        System.out.println("\n=== Sorting Algorithm Properties ===");
        
        String[][] algorithms = {
            {"Bubble Sort", "O(n²)", "In-place", "Stable", "Simple"},
            {"Selection Sort", "O(n²)", "In-place", "Unstable", "Simple"},
            {"Insertion Sort", "O(n²)", "In-place", "Stable", "Small arrays"},
            {"Quick Sort", "O(n log n)", "In-place", "Unstable", "Fast"},
            {"Merge Sort", "O(n log n)", "Out-of-place", "Stable", "Reliable"},
            {"Heap Sort", "O(n log n)", "In-place", "Unstable", "Guaranteed"}
        };
        
        System.out.println("Algorithm\t\tTime Complexity\tSpace\t\tStability\tDescription");
        System.out.println("---------\t\t---------------\t-----\t\t---------\t-----------");
        
        for (String[] algo : algorithms) {
            System.out.printf("%-20s\t%-15s\t%-15s\t%-15s\t%s%n", algo[0], algo[1], algo[2], algo[3], algo[4]);
        }
    }
}

Big-O Notation Overview

Complexity	Description	Example	Growth
O(1)	Constant time	Array access	1
O(log n)	Logarithmic	Binary search	log₂(n)
O(n)	Linear	Linear search	n
O(n log n)	Linearithmic	Merge sort	n·log(n)
O(n²)	Quadratic	Bubble sort	n²
O(2ⁿ)	Exponential	Recursive Fibonacci	2ⁿ

Search Algorithm Comparison

Algorithm	Time Complexity	Prerequisite	Best Use Case
Linear Search	O(n)	None	Small, unsorted arrays
Binary Search	O(log n)	Sorted	Large, sorted arrays
Interpolation	O(log log n)	Sorted, uniform distribution	Numerical data
Jump Search	O(√n)	Sorted	Large arrays with jump size
Exponential	O(log n)	Sorted	Unbounded arrays

Sorting Algorithm Comparison

Algorithm	Time Complexity	Space Complexity	Stable	In-place
Bubble Sort	O(n²)	O(1)	Yes	Yes
Selection Sort	O(n²)	O(1)	No	Yes
Insertion Sort	O(n²)	O(1)	Yes	Yes
Quick Sort	O(n log n)	O(log n)	No	Yes
Merge Sort	O(n log n)	O(n)	Yes	No
Heap Sort	O(n log n)	O(1)	No	Yes

Algorithm Design Principles

Divide and Conquer

1. Divide: Break the problem into smaller subproblems
2. Conquer: Solve subproblems recursively
3. Combine: Merge the solutions

Examples: Quick Sort, Merge Sort, Binary Search

Greedy Algorithms

1. Make locally optimal choices at each step
2. Hope for global optimality

Examples: Dijkstra, Kruskal, Huffman Coding

Dynamic Programming

1. Optimal substructure: Overlapping subproblems
2. Memoization: Cache intermediate results

Examples: Fibonacci, Knapsack Problem

Performance Optimization

Space-Time Tradeoff

// Trade memory for speed
public class FibonacciMemoization {
    private static Map<Integer, Long> memo = new HashMap<>();
    
    public static long fibonacci(int n) {
        if (n <= 1) return n;
        
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        long result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }
}

Early Termination

// Optimized linear search with sentinel
public static int optimizedLinearSearch(int[] array, int target) {
    int n = array.length;
    
    // Check last element first
    if (array[n - 1] == target) {
        return n - 1;
    }
    
    // Replace last element with target
    int last = array[n - 1];
    array[n - 1] = target;
    
    int i = 0;
    while (array[i] != target) {
        i++;
    }
    
    // Restore original value
    array[n - 1] = last;
    
    return i < n - 1 ? i : -1;
}

Strengths and Limitations

Advantages of Algorithm Analysis

• Performance prediction: Estimate runtime behavior
• Algorithm selection: Choose the right approach
• Optimization: Identify bottlenecks
• Scalability: Understand growth patterns

Limitations

• Theoretical assumptions: Ignores constants
• Practical differences: Hardware effects matter
• Complexity: Mathematical analysis is demanding
• Over-engineering: Premature optimization risks

Common Interview Questions

1. What’s the difference between best, average, and worst case? Best case represents the optimal path, average case reflects expected performance, and worst case the poorest scenario.

2. Why is binary search O(log n) and not O(n)? Halving the search space at each step reduces the problem logarithmically.

3. When would you use insertion sort instead of quick sort? For small arrays or nearly sorted data, where insertion sort achieves O(n) performance.

4. What does in-place mean for sorting algorithms? The algorithm sorts without requiring additional memory beyond O(1) space.

Key Resources

1. https://en.wikipedia.org/wiki/Big_O_notation
2. https://www.geeksforgeeks.org/fundamentals-of-algorithms/
3. https://mitpress.mit.edu/books/introduction-algorithms