CS1 Study Guide

Algorithm Analysis

Steps to Analyze Time Complexity

  • Identify the Input Size:

    • Determine the variable representing input size (usually n), such as length of an array or number of elements in a data structure.

  • Analyze Loops:

    • Count how many times each loop runs relative to n.

      • For simple loops, time complexity is proportional to the number of iterations (O(n)).

      • For nested loops, multiply time complexities of each level.

  • Account for Recursive Calls:

    • Set up recurrence relations that represent how input size shrinks with each recursive call.

    • Solve the recurrence using methods such as the master theorem or recursion trees.

  • Consider Constant Operations:

    • Operations within loops or recursive calls that take constant time are counted as O(1) unless they depend on input size.

  • Simplify the Complexity:

    • In Big-O notation, drop constant factors and lower-order terms.

    • Focus on the term with the fastest-growing rate as n increases.

  • Analyze Best, Worst, and Average Cases:

    • Best Case: Minimum number of operations required.

    • Worst Case: Maximum number of operations required (e.g., quicksort O(n^2)).

    • Average Case: Typical performance estimate, usually an approximation.

Big-O Notation Chart

Complexity Descriptions

  • O(1): Constant time

    • Example: Accessing an array element by index.

  • O(log n): Logarithmic time

    • Example: Binary Search, Balanced Binary Search Trees (BST).

  • O(n): Linear time

    • Example: Linear Search, Simple Loops.

  • O(n log n): Log-linear time

    • Example: Merge Sort, Quick Sort, Heap Sort.

  • O(n^2): Quadratic time

    • Example: Bubble Sort, Selection Sort, Insertion Sort.

  • O(n^3): Cubic time

    • Example: Matrix multiplication (naive), Triple nested loops.

  • O(2^n): Exponential time

    • Example: Recursive Fibonacci, Brute-force solutions to NP problems.

  • O(n!): Factorial time

    • Example: Permutation generation, Traveling Salesman Problem (TSP).

Algorithmic Patterns and Their Time Complexities

  • Linear Search O(n): Searches entire data set one element at a time.

  • Binary Search O(log n): Divides search space in half, searching a sorted list.

  • Divide and Conquer O(n log n): Splitting problem into smaller parts, e.g., Merge Sort.

  • Dynamic Programming O(n^2), O(n^3): Solving problems by breaking down into overlapping subproblems recursively.

  • Greedy Algorithms O(n log n): Making locally optimal choices at each step.

  • Backtracking O(2^n): Exploring all possible solutions incrementally.

  • Brute Force O(n!), O(2^n): Trying all solutions to find optimal one.

Solving a Summation

  • Constant Summation: Simplifies to n.

  • Arithmetic Summation: Sum of the first n integers.

  • Geometric Summation: Exponential growth, e.g., Binary Search.

  • Harmonic Summation: Appears in algorithms like Quick Sort.

Examples of Summations

  • Sum of First n Integers: n(n+1)/2.

  • Geometric Progression (Merge Sort): Summing 1, r, r^2... up to n.

  • Harmonic Series: 1 + 1/2 + 1/3 + ... + 1/n.

Summation and Run-Time Analysis Quick Reference

  • n: O(n) - Simple loop.

  • O(n^2): Nested loops.

  • O(log n): Binary Search.

  • O(n^3): Triple nested loop.

  • O(n log n): Merge Sort.

  • Harmonic series: O(log n).

Recurrence Relations Steps to Solve

  1. Identify the recurrence form.

  2. Choose a solution method (substitution, recursion tree, master theorem).

  3. Solve to find the complexity.

Types of Recurrences

  • Divide and Conquer: T(n) = aT(n/b) + O(n^d).

    • a: Number of subproblems.

    • b: Size reduction factor.

    • d: Work done outside recursion.

Master Theorem

Applies to recurrences of the form T(n) = aT(n/b) + O(n^d).

  • Case 1: a > b^d → Solution: O(n^{log_b a})

  • Case 2: a = b^d → Solution: O(n^d log n)

  • Case 3: a < b^d → Solution: O(n^d)

Common Recurrences & Their Solutions

  • T(n) = 2T(n/2) + O(n) → O(n log n)

  • T(n) = 3T(n/4) + O(n) → O(n log n)

  • T(n) = 4T(n/2) + O(n) → O(n log n)

  • T(n) = T(n/2) + O(1) → O(log n)

  • T(n) = T(n/2) + O(n) → O(n)

Algorithm Performance

Algorithm Analysis Table

Algorithm

Best Case

Average Case

Worst Case

Space

Stable

In-Place

Bubble Sort

O(n)

O(n^2)

O(n^2)

O(1)

Yes

Yes

Selection Sort

O(n^2)

O(n^2)

O(n^2)

O(1)

No

Yes

Insertion Sort

O(n)

O(n^2)

O(n^2)

O(1)

Yes

Yes

Merge Sort

O(n log n)

O(n log n)

O(n log n)

O(n)

Yes

No

Quick Sort

O(n log n)

O(n log n)

O(n^2)

O(log n) (in-place)

No

Yes

Example Sorting Algorithms

  • Bubble Sort: Repeatedly compares and swaps adjacent elements until no swaps are needed.

  • Selection Sort: Divides array into sorted and unsorted portions, finds minimum and places in sorted.

  • Insertion Sort: Builds sorted array one item at a time by inserting elements in correct position.

Merge Sort Implementation

  • Divide: Repeatedly splits list into sublists (each one element).

  • Merge: Combines sublists until sorted.

Quick Sort Implementation

  • Partition: Choose a pivot, rearrange elements around pivot, and sort recursively.

Tree Characteristics

Tree Types

  • Binary Tree: Each node has at most two children.

  • Binary Search Tree: Left subtree contains smaller, right larger values.

  • Heap: Complete binary tree maintaining heap property.

  • Trie: Digital tree for string storage.

  • AVL Tree: Self-balancing BST with specific balance factors.

Tree Operations

  • Traversal (Inorder, Preorder, Postorder): Visit nodes in a specific order; each takes O(n).

  • Height Calculation: Recursively computes tree height.

Searching in Trees

  • Linear Search: O(n) - Sequentially checks each node.

  • BST Insertion: O(log n) (balanced) or O(n) (skewed).

  • Deletion: Handles cases based on children; O(log n) (balanced) or O(n) (skewed).

  • Search: Traverses based on value comparisons; O(log n).

Heap Operations

  • Insertion: Add at end, then percolate to maintain heap property; O(log n).

  • Deletion: Replace root with last element, percolate down; O(log n).

  • Heap Construction: O(n) using bottom-up method.

Trie Operations

  • Insertion: Traverse/create nodes for each character in the key; O(k), where k is length of key.

  • Deletion: Remove key, deleting nodes if necessary; O(k).

  • Search: Traverse nodes for each character; O(k).

AVL Tree Operations

  • Insertion: Insert like BST, then rebalance; O(log n).

  • Deletion: Delete and rebalance; O(log n).

  • Search: Traverse to find value; O(log n).

Hash Tables

Definition

  • Collection of key-value pairs where a hash function maps keys to array indices for efficient access.

Features of Hash Tables

  • Efficient Search: Average O(1) for lookups, inserts, deletes.

  • Fixed Size: Typically has a resizing mechanism.

  • Collision Handling: Methods like chaining and open addressing.

  • Order: Does not maintain order as keys are hashed.

Hash Table Operations

  • Insert: O(1).

  • Search: O(1).

  • Delete: O(1).

  • Resize: O(n).

Collision Handling Techniques

  • Chaining: Store multiple pairs in linked lists.

  • Open Addressing: Find next open slot after collision.

Common Problems with Hash Tables

  • Collisions, Load Factor, Poor Hash Function, Resizing.

Example Hash Table Implementation (with Chaining)

  • Structures for HashNode and HashTable, including basic operations (insert, search, delete).

Hash Table Resizing Strategies

  • Resize table when load factor exceeds a certain threshold, usually doubling size.

Hashing Methods

  • Overview of various hash methods like Division Method, Multiplicative Method, Folding Method, and String Hashing.

Collision Handling Methods in More Detail

  • Chaining: Simple linked list storage in linked list at index.

  • Open Addressing: Linear probing, quadratic probing, double hashing - finding next slot within table.