Complexity and Big-O

Code complexity and Big-O notation

If you want to write an outstanding algorithm, you must need to understand the most important concepts such as complexity and big-O notation.

A problem may have many solutions from a different perspective, but we need to choose the best one out of them.

In this short and precise tutorial, I will try my best to explain the important concepts with little examples.

So, what is code complexity?

Code complexity just means how much your code is complex with respect to time(execution time) and space(memory).

Before diving into the detail, we have to understand these three concepts

  1. Big-O (worst case) the maximum time to execute set of operations or you can say the slowest time when the input size increases.
  2. Omega Ω (Best case) the fastest or minimum time to execute our code. E.g., in searching algorithm, our required number found at the first position in the array
  3. Theta Ɵ. The average time to execute our code, e.g., the required number in the middle of the array

Simple example

Suppose we have an array with five elements and we want to find out some number from the given array.

The rule is: Find item step-by-step order

Best Case Scenario

Suppose we are looking for a number 8, but the rule is, find any number from array in progressive  order, and when we iterate the array to find our required number, we have found that number at the very first position which is the best case Omega Ω  or required the minimum time to find our desired number.

We analyze our algorithm when the input size and number of operations are unknown or unexpected which is known as the worse case.

Average (mid) Case scenario

And suppose that we are looking for a number called 3 which can be found in the middle of the array after average number of iteration or average number of try, this type of scenario called the average case scenario or the Theta  Ɵ

Worst Case scenario (Big – O):

And also suppose that we are looking for a number called 7 which can be found at the end of the array after maximum iteration or maximum number of try, this type of scenario called the Worst case scenario or the Big – O

In simple word, we need (n) time to find out any number.

So, in every algorithm we must take care of the Worst case scenario but why not others case scenario, because the best case and average case run fast or normal so why we care about them.

We can represent this three scenario in graph level

There are different level of complexity

Big-O = O

If we are working with an algorithm which has higher level of time complexity, then we should try another algorithm with low level of complexity to solve out the same problem

For example, we are working with sorting algorithm and unfortunately using the  selection sort which higher level of complexity then we must need to replace selection sort with any other algorithm which must have the lower level of complexity such as merge sort or heap sort, in this way we can make our operations efficient in less time.

 

 

In the next tutorial, we will learn that how to calculate the Big-O of the algorithm, and we will demonstrate some basic example. Also, I have uploaded a complete summary of Big-O for the most used algorithms.