Exploring Big O Notation

Meet the Author: Marco Ni

Hello Readers! This tutorial will introduce the basic principles of Big O Notation and how to analyze the performance of algorithms.

What is Big O Notation?

Big O notation is all about describing the maximum time or space that an algorithm may require as the size of the input increases.

It’s a way to show us the worst-case situation for how an algorithm performs, which helps us get a grip on what the algorithm does when the input size gets bigger.

Common Big O Notations

1. O(1) – Constant Time Complexity
   • The running time of the algorithm does not change with the input size.
   • Example: Accessing an element in an array by index.
2. O(n) – Linear Time Complexity
   • The running time grows linearly with the input size.
   • Example: Finding the maximum value in an unsorted list.
3. O(n^2) – Quadratic Time Complexity
   • The running time grows quadratically with the input size.
   • Example: Bubble Sort or Insertion Sort algorithms.
4. O(log n) – Logarithmic Time Complexity
   • The running time grows logarithmically with the input size.
   • Example: Binary Search in a sorted array.
5. O(n log n) – Linearithmic Time Complexity
   • The running time grows proportionally to n log n.
   • Example: Merge Sort or Quick Sort algorithms.
6. O(2^n) – Exponential Time Complexity
   • The running time doubles with each additional element in the input.
   • Example: Solving the Traveling Salesman Problem using brute force.

How to Analyze Algorithm Complexity

1. Identify the Basic Operations
   • Determine the fundamental operations of the algorithm, such as comparisons, assignments, or iterations.
2. Determine the Input Size
   • Establish how the size of the input affects the number of operations.
3. Calculate the Running Time
   • Express the running time in terms of the input size n. For example, if an algorithm requires iterating through a list of size n, it has a linear time complexity O(n).
4. Simplify the Expression
   • Focus on the term with the highest growth rate and discard constants and lower-order terms. For example, O(3n^2 + 5n) simplifies to O(n^2).

Examples

1. Linear Search
   • Algorithm: Search for a value in a list by checking each element sequentially.
   • Time Complexity: O(n)
   • Reason: In the worst case, the algorithm must check every element.
2. Binary Search
   • Algorithm: Search for a value in a sorted array by repeatedly dividing the search interval in half.
   • Time Complexity: O(log⁡ n)
   • Reason: Each step reduces the problem size by half.
3. Bubble Sort
   • Algorithm: Sort a list by repeatedly swapping adjacent elements if they are in the wrong order.
   • Time Complexity: O(n^2)
   • Reason: It requires nested loops, with each loop iterating over the list.
4. Merge Sort
   • Algorithm: Sort a list by dividing it into halves, sorting each half, and then merging them.
   • Time Complexity: O(n log⁡ n)
   • Reason: The list is divided logarithmically, and merging takes linear time.

Works Cited

1. Introduction to Big O Notation – GeeksforGeeks
   • https://www.geeksforgeeks.org/analysis-of-algorithms-set-1-asymptotic-analysis/
2. Understanding Big O Notation – Techopedia
   • https://www.techopedia.com/definition/26258/big-o-notation