Algorithms

From this part of the notes onward, mostly python will be used as program code. In the syllabus python, java and visual basic are all allowed but I am using python as it is the easiest.

Algorithm Performance

• Different algorithms can perform the same task, but may vary in efficiency
• Criteria for comparison
  • Time complexity: How long an algorithm takes to complete a task.
  • Space complexity: How much memory an algorithm uses while running.

Big O Notation

• A mathematical notation used to describe the upper bound of an algorithm’s running time or memory usage as input size grows.
• Focuses on the worst-case scenario.
• Common Big O examples:
  • O(1): Constant time - execution time does not depend on input size.
  • O(n): Linear time - execution time grows linearly with input size.
  • O(n²): Quadratic time - execution time grows with the square of input size.
  • O(log n): Logarithmic time - execution time grows slowly as input increases.

Searching Algorithms

Linear Search

Simple searching algorithm that checks each element in a list or array sequentially until it finds the desired value.
Time Complexity: O(n)
Space Complexity: O(1)

No output yet.

Binary Search

• It works by repeatedly dividing the search range in half until the item is found or the range becomes empty.
• Instead of checking every item, binary search quickly narrows down where the item could be.
• Necessary Condition: The data must be sorted
• As more items are added, the time increases, but since the data is halved each time, it grows more slowly and eventually becomes almost constant
• Time Complexity:
  • Best Case: O(1) - The target is found at the middle element
  • Worst/Average Case: O(log₂ n)
• Space Complexity: O(1)

No output yet.

Sorting Algorithms

Insertion Sort

Insertion sort builds a sorted list one element at a time by inserting each item into its correct position.

• Time Complexity:
  • Best case: O(n) (already sorted)
  • Worst case: O(n²) (reverse order)
• Space Complexity: O(1)

No output yet.

Bubble Sort

Sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order and iterates until the list is sorted.
Time Complexity:

• Best case: O(n) (optimized version, already sorted)
• Worst case: O(n²) (reverse order)

Space Complexity: O(1)

No output yet.