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

This guide covers algorithm fundamentals in depth—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; sort algorithms order data.

Concise 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: Number of operations as a function of input size
• Space complexity: Memory required to run the algorithm
• Big-O notation: Upper bound of an algorithm’s complexity
• Best/Average/Worst case: Different runtime scenarios

Most Common Big-O Classes:

• 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

Exam-Relevant Points

• Algorithms: Well-defined instruction sequences for problem-solving
• Big-O notation: Mathematical description of complexity
• Time complexity: Number of operations relative to input size
• Search algorithms: Linear Search (O(n)), Binary Search (O(log n))
• Sort algorithms: Bubble Sort (O(n²)), Quick Sort (O(n log n))
• Best/Worst/Average case: Different runtime scenarios
• Industry-relevant: 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. Sort 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) for each 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 performed");
        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) average case
    // 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 range where element might exist
        int i = 1;
        while (i < n && sortedArray[i] <= target) {
            i = i * 2;
        }
        
        // Binary search in 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 block where element might exist
        while (sortedArray[Math.min(step, n) - 1] < target) {
            prev = step;
            step += (int) Math.sqrt(n);
            if (prev >= n) {
                return -1;
            }
        }
        
        // Linear search within 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;
            }
            
            // Pick 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\tPrerequisite\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 the minimum in the unsorted portion
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            
            // Swap the minimum with the 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 the 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];  // 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 the 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 Algorithm 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 Reference

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 Algorithms Comparison

Algorithm	Time Complexity	Requirement	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, uniformly distributed	Numerical data
Jump Search	O(√n)	Sorted	Large arrays with jump size
Exponential	O(log n)	Sorted	Infinite arrays

Sorting Algorithms 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 together

Examples: Quick Sort, Merge Sort, Binary Search

Greedy Algorithms

1. Make locally optimal decisions 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

// Trading 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 for the problem
• Optimization: Identify performance bottlenecks
• Scalability: Understand growth patterns as input size increases

Limitations

• Theoretical assumptions: Ignores constant factors
• Practical differences: Hardware-dependent variations
• Analysis complexity: Mathematical analysis can be involved
• Premature optimization: Risk of optimizing before profiling

Common Interview Questions

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

2. Why is binary search O(log n) and not O(n)? Because the algorithm halves the search space at each step, achieving logarithmic time instead of linear.

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

4. What does in-place mean for sorting algorithms? The algorithm sorts the data using only O(1) additional space, modifying the original array without requiring extra memory.

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