Introduction to Big O Notation in Data Structure

Download ebook

Big O Notation in data structure is mainly used in the field of mathematics and computer science. It informs us of an algorithm’s performance in a given situation. The term “Algorithm” sounds like a complicated mechanism. But in simple terms, it is a set of instructions to be followed in a sequence to arrive at an output. The need to apply algorithms arose on account of the voluminous data the company has to deal with on a daily basis.

Algorithms have brought about a revolutionary change in this competitive digital world. The Big O notation in data structure helps to identify the most efficient algorithm as a solution to the problem.

What is big O notation in data structure?

Big O Notation in data structure is an advanced mathematical notation to define the efficiency of an algorithm. The letter “O” stands for “Order of”. The computer executes it in a step-by-step manner. It accepts an input and converts it into an output. So, O(N) stands for “Order of N” in which N represents the input size. It states the number of steps an algorithm takes in accordance to the size of input.

All the companies are dealing with some problems. In order to solve them, the companies list out various steps. These steps are called algorithms. These problems might have multiple solutions in the form of several algorithms. So, the challenge lies in picking-up the best solution that saves time and occupies less memory. This is termed as Algorithm analysis.

In the multiple solutions, the Big O notation has to conduct a search operation. So, let us use the Linear search and the Binary search to understand the process of Big O notation.

Linear Search

In this method, an element is searched from a whole list of data until a match is found. The assumption is that the data is sorted in sequence. So, the number of steps to be followed will depend on the length of the array. It means if there are 1 million data in a series, the algorithm will perform 1 million steps to search for the target element. As the size of input increases, the number of steps to search will correspondingly increase. So, the time complexity is quite high.

Example –

2

4

6

8

9

12

14

16

18

20

In the above table, there are 10 numbers. Let us consider that the target element to be searched is number 12. So, the algorithm matches each and every value in the box with number 12. As its search activity reaches Box No.6, it finds a match and displays the result. So, it had to perform six steps to get the answer. If the position of number 12 was in the last box, then the algorithm would have to perform 10 steps. In the worst case, if the target element is not in the list, then the algorithm gives the result as “Not found”. So, the instruction is always to conduct an entire search.

Binary Search

In this approach, the target element is not matched with individual data in the whole list. The algorithm divides the whole array into two parts. So, the Big O notation divides the total number of records by two to arrive at the mid value. Then it compares the mid value with the target element. If it does not match, it further checks whether this mid value is greater or less than the target element. So, if the mid value is greater, then all the values higher than the mid value are excluded in the next search. If the mid value is lower, then all the values lower than the mid value are excluded in the next search. Then it again divides the remaining records by two to arrive at its mid value and the search continues.

So, at every stage of operation, it reduces the search records by 50% while calculating the mid value.

Example –

2

4

6

8

9

12

14

16

18

20

Let us consider the same set of 10 numbers with the target element again as 12. So, in this method, 10 is divided by 2 which gives us the answer 5. So, the fifth number in the table is 9 which becomes the mid value. Now, Big O notation compares 9 with the target element 12. Since, mid-value is less than 12, the number 9 and the numbers less than 9 will not be a part of the next search. So, it has removed half of the numbers for the next operation. Subsequently, only the numbers in the remaining 5 boxes will be considered for the next search. In the next operation, the mid value is 16 which is higher than the target element. So, it again removes the number 16 and all the numbers higher than 16 from the next search.

So, we are left with only 12 and 14. Now the algorithm will find its match in the next operation. So, from the same set of numbers, the Binary approach follows only 4-5 steps to find the target element. Even if the total records are in millions, this approach will provide the answer with just a few more steps.

The Big O notation and Time Complexity

Time Complexity is the measure of increase in the running time of an algorithm when there is an increase in the input data. In the Linear approach, the Big O notation is denoted as O(n).  In the Binary approach, it is denoted as O(log n). The Big O adopts the worst-case scenario to indicate the longest time an algorithm takes to perform.

So, the big O notation in data structure compares the number of operations performed by the Linear and the Binary method. From the above calculation for Linear search, it is clear that its running time will grow exponentially with 10 times increase in the input data. However, the running time for Binary search will increase only slightly, even if the input data increases by 10 times. With Big O notation, the developers can classify algorithms based on their runtime analysis.

Types of complexities in algorithms

1	O(1)	Constant time
2	O(log n)	Logarithmic time (used in Binary search)
3	O(n)	Linear time (used in Linear search)
4	O(n log n)	Linearithmic time
5	O(n^2)	Quadratic time
6	O(2^n)	Exponential time
7	O(n!)	Factorial time

From the above list, the first two complexities can be considered as time-efficient.  The companies can adopt the third complexity though its running time is more than the first two. But the remaining four complexities have a very long execution time. Considering the time constraints, it will not be practical to adopt them in the production environment. So, it would be advisable for companies to focus on the first three complexities.

Henry Harvin Education

For a deeper understanding on the Big O notation, two courses from Henry Harvin can be helpful to the readers. They are Artificial Intelligence Course and Machine Learning Course Using Python | CMLP Certification

Conclusion

The Big O notation in data structure provides the lower and upper boundaries of the algorithm’s running time. It compares various algorithm solutions based on its execution time and the space occupied in the memory. From this result, the company can implement the most efficient algorithm to solve their problems. All in all, the Big O notation in data structure is a valuable tool to analyze the complexities of algorithms.

FAQs

Download ebook