Big-O Notation | Measuring Time Complexity | Worst-Case Complexity

Efficiency comes in two flavors. Time and space efficiency are the two. The speed of an algorithm is indicated by its time complexity or efficiency. Memory usage for input and output is indicated by space complexity or efficiency. The quantity of space needed by an algorithm is not as important now that technology and memory capacity have advanced. The time problem, however, has not made as much progress.

There are three asymptotic notations to find out time efficiency of algorithms. They are:

Big-O , Big-Ω (Omega) and Big-θ (Theta).

In this section, We will discuss about Big-O notation which is also called worst-case complexity. It represents upper bound of the running time of an algorithm. We can compute Big-O of an algorithm by counting iteration number count of an algorithm in worst-case scenario with an input of N.

Quick Note: O(log n) is the Big-O notation for binary search algorithm.

Big-O notation of Linear Search Algorithm:

Linear Search Algorithm searches all elements in given array in sequential manner.

Take an array with the following elements: 1, 4, 3, 7, 21.

Note: This method can be performed on both sorted and unsorted arrays. Searching in both arrays starts from 0th position.

We must extract the number that is larger than or equal to 21 from this array.

The best case complexity to find the number that satisfies given condition in linear search will be when the element we are searching is in first position. therefore O(1) will represent the best case complexity.

The number we are looking for is at the last place of the given array, hence our program will make ‘n’ comparisons for an array of length n.

Hence, O(n) represents the worst-case complexity for a linear search algorithm.

Below is the Linear Search algorithm implemented in Java.

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i; // return the index of the target element if found
        }
    }
    return -1; // return -1 if the target element is not found in the array
}

Thanks for reading the article.

References: Data Structures and Algorithms made easy

Some automation needed for your server? Then find out here: Setup Ansible In your Servers