The Big O notation

Understanding big O notation in Data Structures and Algorithm

Introduction

There are several ways to solve a problem, to choose the best algorithm to use, we need to compare the performance of the different algorithms. Comparing the performance of an algorithm is achieved by measuring it’s space and time complexity.

we need to be conversant with the big O notation to be able to approach problems with least time and resources.

Big O notation is a way of measuring an algorithm’s efficiency in terms of the time it takes to run your function as in out grows. N.B it does not tell you the speed of an algorithm in seconds rather by the number of operation they take.Big O (O()) describes the upper bound of the complexity.

Two parts of measuring algorithm’s efficiency

• Time Complexity is the amount of time taken by an algorithm to run with the change in size input.
• Space Complexity finds out how much (extra)space/memory will be required by an algorithm with change in input.
• Order of growth is how the time of execution depends on the length of the input which helps us compute the running time with ease.

Common algorithms and their run time in big O notation. The algorithms are categorized in two:

Sequential algorithm a list or array is traversed sequentially and every element is checked. Example Linear search

Interval Search algorithms are specifically designed for searching in sorted data-structures.They are more effective than linear algorithms because they divide the search space in half and repeatedly target the center of the search structure. Example Binary Search

• O(log n) — Binary search.
• O(n) —Linear search.
• O(n * log n) — Quick sort.
• O(n2) — Selection sort.
• O(n!) — Traveling salesperson

1. Linear search (O(n))

Iterating through a list of elements until you find element that you looking for. Let’s take an example of an array.

int[] myArray = {1, 3, 5, 7, 9, 11, 13, 14, 15};

This algorithm takes O(n) times to execute. Let’s assume you are searching for number 11 in the array ,in the worst case you will have to search through every single number in the array(n times) where n is the number of elements in the list, the best case will be when the number 11 is the first element in the array O(1).

O(1) is the best scenario but big O notation focuses on the worst case O(n) for a linear search. The example above will take 6 iterations before number 6 is found.

Example

Given an array arr[] of N elements, the task is to write a function to search a given element x in arr[]. If x doesn’t match with any of the elements, return -1.

Steps to implement linear search

• Start from the leftmost element of arr[] and one by one compare x with each element of arr[]
• If x matches with an element, return the index.

2. Binary Search (O(Log n))

This is a searching algorithm used in a sorted array by repeatedly dividing the search interval into half. It uses the information that the array is sorted and reduce the time complexity to O(Log n).

Steps to perform a binary search

• Begin with the mid element of the whole array as a search key.
• If the value of the search key is equal to the item then return an index of the search key.
• Or if the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.
• Otherwise, narrow it to the upper half.
• Repeatedly check from the second point until the value is found or the interval is empty.

Given a sorted array arr[] of n elements, write a function to search a given element x in arr[] and return the index of x in the array

3. Ternary Search (O(log3n))

This algorithm is similar to the binary search since it divides an array into sub-array. Ternary search splits/divide an array into three parts and determine which part has the search element. The array is divided into three parts using mid1 and mid2, where l=0 and r=n-1, n is the length of the array.

Ternary search time complexity:O(log3n) and space complexity is : O(1)

N.B To perform a ternary search, you need a sorted array.

To calculate mid1 and mid2 use the formula below:

mid1=l +(r-l)/3;

mid1=r -(r-l)/3;

Steps implement ternary search

• Compare the key with the element at mid1. If found equal, we return mid1.
• If not found in step 1, then compare the key with the element at mid2. If found equal, we return mid2.
• If not found in step 2, then check whether the key is less than the element at mid1. If yes, then recur to the first part.
• If not, then we check whether the key is greater than the element at mid2. If yes, then recur to the third part.
• If not, then we recur to the second (middle) part.

There are many other algorithms you can learn, checkout javatpoint, tutorialspoint, geekforgeeks etc for more resources.

Happy coding!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!