Big-O Cheat Sheet for Some Data Structures and Algorithms.
- Types of Asymptotic Notation Big-Oh Notation Example: 4n2 +2 ∈ O(n2) 0 10 20 30 40 50 60 70 80 90 0 0.5 1 1.5 2 2.5 3 3.5 4 4.x.2 + 2 x.2 5.x.2 Mike Jacobson (University of Calgary) Computer Science 331 Lecture #7 5 / 19.
- Asymptotic Notation is used to describe the running time of an algorithm - how much time an algorithm takes with a given input, n. There are three different notations: big O, big Theta (Θ), and big Omega (Ω). Big-Θ is used when the running time is the same for all cases, big-O for the worst case running time, and big-Ω for the best case running time.
Are you writing software an any programming language? If yes, have you ever wondered while writing even a simple iteration or recursive method how good or bad is it? In this article I will try to analyse my algorithm which I have written to get some end results. I will use C# as the language. I will use big O notation to find the worst case complexity.
Understanding Big O notation With C# Code
And if we are writing our software without even having a small idea of this concept, we are doing a huge injustice to product which we are developing. Lets start by analysing a small code.
As you can see in the above code I have a simple functions. In the function I am getting an item from the collection of 10 items if the the item is found otherwise I am simply returning null.
Lets take the letter 'c'. Suppose if I want to find if 'c' is present or not. The line number 6 will execute only once as the record is present at the first position or zero index.
Now suppose if I am passing 'j' letter as parameter which I need to find. In the list we can see that line number 6 will execute 10 times as it is present at the last of the array. This is the worst case scenario which we have discussed just now of finding 'j' for this function.
You will get a more clear understanding using the figure below.
If I have to execute the same method for n number of items in the array. The worst case scenario in that case would be n. This is what is known as Big O notation. We can also also denote big O for this method as O(n).
In another case suppose we have to find all the n number of items in the array whose size is n. We are performing a linear search in the above case by traversing all the items one by one.
In this part of the article I will discuss a more faster way to search items in the array. This search is known as binary search. We will also try to find the worst case time complexity of binary search. Lets assume that we have same array as sorted.
In binary search algorithm, the array is divided in two parts in one step by the middle element. Lets see the below figure for reference.
The array is sorted in ascending order.
Step 1: The algorithm will find the middle element, 'f' in this case.It will see that 'j' (the element which we are looking for) is on the right side.It will neglect all the other elements i.e. a, b, c, d, e.
Step 2: Now the next middle element is 'h' amongst the remaining elements. It will check that the element 'j' is not equal to 'h' and it is still present on the right side. It will ignore the elements f and g.
Step 3: Amongst h, i, j. 'i' is the middle element which is not equal to 'j'. Now 'h' is ignored.
Big O Notation Calculator
Step 4: Among 'i' and 'j'. The pointer points to the next element which is 'j'. The algorithm sees that this is the same element which we are looking for and it returns the element.
Lets find the worst case complexity of binary search.
To find the complexity we should know about exponential functions. Please see below calculation for better understanding.
In the above calculations we can see with every multiplication our output is growing at huge rate.Taking the case of binary search, the output in the above calculations are the number of elements. It means to search for number of iterations for array containing between 16 and 32 elements is same i.e 5 .
Big O Notation Cheat Sheet
To know the worst case complexity for finding the element in an array of size of N is (log base 2 (N)) which is very small in comparison to linear search.
For example,To find an element in a sorted array containing 1 Crore elements , the worst case complexity is 24.
Conclusion:
In this article I have discussed about the big O notation. I also discussed about how to calculate big O notation using C# code example and compared linear and binary search.
My Learning Resource
Step 4: Among 'i' and 'j'. The pointer points to the next element which is 'j'. The algorithm sees that this is the same element which we are looking for and it returns the element.
Lets find the worst case complexity of binary search.
To find the complexity we should know about exponential functions. Please see below calculation for better understanding.
In the above calculations we can see with every multiplication our output is growing at huge rate.Taking the case of binary search, the output in the above calculations are the number of elements. It means to search for number of iterations for array containing between 16 and 32 elements is same i.e 5 .
Big O Notation Cheat Sheet
To know the worst case complexity for finding the element in an array of size of N is (log base 2 (N)) which is very small in comparison to linear search.
For example,To find an element in a sorted array containing 1 Crore elements , the worst case complexity is 24.
Conclusion:
In this article I have discussed about the big O notation. I also discussed about how to calculate big O notation using C# code example and compared linear and binary search.
My Learning Resource
Excel your system design interview
