Algorithms
What is Algorithms?
The process of rearranging the elements of a collection into a specific order.
Key formula / rule: Time Complexity (Worst Case)
Key points
- Understand the principles behind various sorting algorithms.
- Analyze the time and space complexity of different sorting algorithms.
- Implement common sorting algorithms.
- Choose the most appropriate sorting algorithm for a given problem.
Common exam trap
Confusing average-case and worst-case complexities.
Definitions
- Term
Sorting
- Meaning
The process of rearranging the elements of a collection into a specific order.
- Term
Time Complexity
- Meaning
A measure of the amount of time taken by an algorithm to run as a function of the length of the input.
- Term
Space Complexity
- Meaning
A measure of the amount of memory space used by an algorithm to run as a function of the length of the input.
- Term
Stable Sort
- Meaning
A sorting algorithm that preserves the relative order of equal elements in the input.
- Term
In-place Sort
- Meaning
A sorting algorithm that requires only a constant amount of additional memory space (O(1)) beyond the input array itself.
Learning objectives
Understand the principles behind various sorting algorithms.
Analyze the time and space complexity of different sorting algorithms.
Implement common sorting algorithms.
Choose the most appropriate sorting algorithm for a given problem.
Formulae
- Name
Time Complexity (Worst Case)
- Note
Applies to Bubble Sort, Insertion Sort, Selection Sort.
- Expression
O(n2)
- Name
Time Complexity (Average Case)
- Note
Applies to Merge Sort, Quick Sort, Heap Sort.
- Expression
O(n log n)
- Name
Time Complexity (Worst Case)
- Note
Applies to Merge Sort, Heap Sort.
- Expression
O(n log n)
- Name
Time Complexity (Worst Case)
- Note
Applies to Quick Sort (with poor pivot selection).
- Expression
O(n2)
Prerequisites
Basic data structures (arrays, lists).
Understanding of time and space complexity analysis (Big O notation).
Recursion (for Merge Sort, Quick Sort).
Common mistakes
Confusing average-case and worst-case complexities.
Incorrectly implementing recursive calls in divide-and-conquer sorts.
Forgetting to handle edge cases like empty lists or lists with one element.
Misunderstanding the pivot selection in Quick Sort.
Assuming all O(n log n) sorts perform equally well in practice.
Keywords
Sorting
Bubble Sort
Insertion Sort
Selection Sort
Merge Sort
Quick Sort
Heap Sort
Time Complexity
Space Complexity
Big O Notation
Stable Sort
In-place Sort
Practice preview
Which of the following is NOT a property of a Binary Search Tree (BST)?…
medium
Which of the following algorithms is used to find the Minimum Spanning Tree (MST) of a connected, undirected graph?…
hard
Which of the following sorting algorithms has the best worst-case time complexity?…
easy