Algorithms Notes

1. What is an Algorithm?

• An algorithm is a step-by-step procedure to perform a task.

• Used in computing for:

  • Finding shortest paths in graphs (e.g., GPS navigation).

  • Searching for patterns (e.g., Google Search).

  • Sorting and searching operations.

2. Total Orders

• Total order: A system where every pair of elements has a defined comparison (greater/lesser).

• Examples:

  • Numbers: 1<2<31 < 2 < 31<2<3

  • Words: Alphabetical order (e.g., "forest" < "forever").

3. Sorting Algorithms

Selection Sort

• Divides the list into:

  1. Sorted sublist (left).

  2. Unsorted sublist (right).

• Steps:

  1. Find the smallest element in the unsorted sublist.

  2. Swap it with the leftmost unsorted element.

  3. Move boundary between sorted/unsorted sublists.

  4. Repeat until the list is sorted.

• Example: Sorting [5,4,3,7,1]

  • Pass 1: [1,4,3,7,5]

  • Pass 2: [1,3,4,7,5]

  • Pass 3: [1,3,4,7,5]

  • Pass 4: [1,3,4,5,7]

  • Final: [1,3,4,5,7]

• Time Complexity:

  • O(n2)O(n^2)O(n2) (quadratic time)

Bubble Sort

• Steps:

  1. Compare each element with its neighbor.

  2. Swap if the left element is greater.

  3. Repeat passes until the list is sorted.

• Example: Sorting [5,4,3,7,1]

  • Pass 1: [4,3,5,1,7]

  • Pass 2: [3,4,1,5,7]

  • Pass 3: [3,1,4,5,7]

  • Pass 4: [1,3,4,5,7] ✅ Sorted!

• Time Complexity:

  • O(n2)O(n^2)O(n2) (quadratic time)

• Note: Bubble Sort is inefficient compared to other sorting algorithms.

4. Searching Algorithms

Binary Search (For Sorted Lists)

• Faster than linear search.

• Steps:

  1. Check the middle element.

  2. If it's equal to the target, return the index.

  3. If it's smaller, search the right half.

  4. If it's larger, search the left half.

  5. Repeat until found or list is empty.

• Example: Find 7 in [-3, -1, 4, 6, 8, 12, 15, 23, 24]

  1. Middle = 6 → 7 is larger → Search right half.

  2. New Middle = 12 → 7 is smaller → Search left half.

  3. New Middle = 8 → 7 is smaller → Search left half.

  4. Empty list → 7 is not found.

• Time Complexity:

  • Best case: O(1)O(1)O(1) (if found immediately).

  • Worst case: O(log⁡n)O(\log n)O(logn) (logarithmic time).

• Used in:

  • Dictionaries (finding words quickly).

  • Large datasets (faster search).

5. Time Complexity Summary