Big Oh Notation

Big O Notation

Big O Notation is a mathematical notation used in computer science to describe the performance or complexity of an algorithm in terms of time and space as the input size grows. It provides a high-level understanding of how an algorithm scales and is used to express the worst-case scenario of an algorithm’s growth rate.

Purpose of Big O Notation

Big O notation helps to:

1. Classify algorithms by their performance and efficiency.
2. Compare algorithms in terms of how they handle increasing input sizes.
3. Evaluate scalability, allowing us to predict how an algorithm behaves when the input size becomes very large.

How It Works

Big O notation expresses the upper bound of an algorithm’s runtime or space usage in relation to the size of the input (usually denoted as n). It focuses on the dominant term, ignoring constants and lower-order terms because they become less important as the input size grows.

For example:

• An algorithm with a complexity of O(2n + 5) is simplified to O(n) because as n increases, the constant 5 and the coefficient 2 become negligible.

Common Big O Notations

Here are some common Big O notations, ordered from best (fastest) to worst (slowest) in terms of time complexity:

1. O(1) – Constant Time

   • Description: The algorithm takes the same amount of time regardless of the input size.
   • Example: Accessing an element in an array by its index.
   • C++ Example:

     int arr[5] = {10, 20, 30, 40, 50};
     int element = arr[2];  // O(1)
     

   • Explanation: Accessing an element by index takes the same time no matter how large the array is.

2. O(log n) – Logarithmic Time

   • Description: The time increases logarithmically as the input size grows. This usually happens when the input is repeatedly divided in half.
   • Example: Binary Search.
   • C++ Example:

     int binarySearch(int arr[], int size, int target) {
         int low = 0, high = size - 1;
         while (low <= high) {
             int mid = (low + high) / 2;
             if (arr[mid] == target) return mid;
             else if (arr[mid] < target) low = mid + 1;
             else high = mid - 1;
         }
         return -1;
     }
     // O(log n)
     

3. O(n) – Linear Time

   • Description: The time grows linearly with the input size. If the input doubles, the time also doubles.
   • Example: Traversing an array.
   • C++ Example:

     void printArray(int arr[], int size) {
         for (int i = 0; i < size; i++) {
             cout << arr[i] << " ";
         }
     }
     // O(n)
     

4. O(n log n) – Linearithmic Time

   • Description: A combination of linear and logarithmic time, often found in efficient sorting algorithms.
   • Example: Merge Sort, Quick Sort.
   • C++ Example (Merge Sort):

     void merge(int arr[], int l, int m, int r) {
         // Merging logic
     }
     
     void mergeSort(int arr[], int l, int r) {
         if (l < r) {
             int m = l + (r - l) / 2;
             mergeSort(arr, l, m);
             mergeSort(arr, m + 1, r);
             merge(arr, l, m, r);
         }
     }
     // O(n log n)
     

5. O(n²) – Quadratic Time

   • Description: The time increases quadratically as the input size grows. If the input size doubles, the time becomes four times longer. This usually happens in algorithms with nested loops.
   • Example: Bubble Sort, Selection Sort.
   • C++ Example (Bubble Sort):

     void bubbleSort(int arr[], int n) {
         for (int i = 0; i < n - 1; i++) {
             for (int j = 0; j < n - i - 1; j++) {
                 if (arr[j] > arr[j + 1]) {
                     swap(arr[j], arr[j + 1]);
                 }
             }
         }
     }
     // O(n²)
     

6. O(2ⁿ) – Exponential Time

   • Description: The time doubles with every additional element in the input. This is typical for recursive algorithms that explore all possible configurations.
   • Example: Solving the Tower of Hanoi problem.
   • C++ Example:

     void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
         if (n == 1) {
             cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod << endl;
             return;
         }
         towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
         cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << endl;
         towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
     }
     // O(2ⁿ)
     

7. O(n!) – Factorial Time

   • Description: The time grows extremely fast as the input size increases. This usually happens when the algorithm needs to generate all possible combinations of the input.
   • Example: Solving the Traveling Salesman Problem with brute force.

Graphical Representation of Big O

If we graph these notations with input size on the x-axis and time/operations on the y-axis, it looks like this:

1. O(1): Flat line (constant time).
2. O(log n): Slowly increasing curve.
3. O(n): Straight line (linear growth).
4. O(n log n): Curve that grows faster than O(n) but slower than O(n²).
5. O(n²): Steep curve, growing faster than linear.
6. O(2ⁿ): Very steep curve, grows exponentially.
7. O(n!): Grows extremely fast as n increases.

Best, Worst, and Average Case

When analyzing an algorithm's complexity, you usually look at three different cases:

1. Best Case: The minimum time an algorithm takes to run. For example, in linear search, the best case is finding the element at the first position (O(1)).
2. Worst Case: The maximum time an algorithm takes to run. For example, in linear search, the worst case is not finding the element and having to search through the entire array (O(n)).
3. Average Case: The expected time an algorithm will take on average. For example, on average, linear search will look through half the elements (O(n)).

Why Ignore Constants in Big O?

In Big O notation, we ignore constants and smaller terms because they don’t matter much when the input size grows large. For example, an algorithm with a time complexity of O(2n + 5) is simplified to O(n), because the 2 and 5 become insignificant as n grows.

Example: Linear Search

Let's say you have an unsorted array and want to find a specific element using linear search.

• Worst Case: You might have to look through the entire array to find the element, so the complexity is O(n).
• Best Case: If the element is the first in the array, the complexity is O(1).
• Average Case: On average, you will look through half the array, so it’s still O(n).

Conclusion

Big O notation helps you classify algorithms based on how they behave with increasing input size. It focuses on the worst-case scenario, simplifying the analysis and helping developers choose the most efficient algorithms for large-scale problems.