The Big O Notation

 



What is the Big O notation is and should why web developers should know about it?

The big O notation also known as Landau’s symbol discovered by a German number theoretician Edmund Landau. It is used to determine the asymptotic nature of functions and to measure their rate of growth– this rate of growth of a function is also referred to a functions Order where the letter O is derived from.

Below are the three common types of algorithms used to describe a functions asymptotic behavior (HyperionDev, 2021):

  • The Constant Function O(1) – describes a function whose complexity rate remains constant regardless of the input size.
  • The Linear Function O(n) – describes a function whose complexity is directly proportionate to the growth in size of the input.
  • The Exponential Function O(2n) – describes a function whose complexity grows exponentially as the size of the input set grows.

The big O notation is relevant in web development as it is used for analysing algorithms which are the set of rules in the calculation that are included in our code. Through it, we can write code that is efficient considering the following factors in efficiency:

  • Execution speed of the algorithm
  • The algorithm’s memory footprint and resources it uses

·

The quadratic function (O(n 2 ))

A quadratic function describes a function that grows to the square of the input set. This can be illustrated in the nested loop shown below where:

  • To create the pattern shown in the ‘result comment’ we have the outer loop that will be called out as long as the value of a is less or equal to 5.
  • with the internal loop, b is called out as long as the value of b is less or equal to a and every time this is true 1 will be added to b to continue the loop.
  • for every time the expression b <= a is true then "*" is displayed on the console
  • for every time a <= 5 is true  a blank ('') string is displayed on the console

Through this nested loop we see that through the input of 5 the function ran 25 different operations to be fully executed thus illustrating how a function with a complexity of O(n2 ) grows to the square of the input set.

Linear search VS Binary search algorithm

A linear search will search an item through going through the list one item at a time until it finds a match. 

As shown in the image above to find the index of b the what the function will do is just compare the items in the list with b until it finds a match and return the index of 1. It has a complexity of O(n) because its complexity is directly proportionate to the growth in size of the input.

 

A Binary Search will search for an item from the middle of a sorted list and see if it matches the median if not then it checks if it is greater or less than the median. 

As shown in the image above the search starts from middle on the entire list and if the median does not match b and is higher than the median in the list then the right half of the list will be searched and the loop will run again. If b is less than the median in the list then the left portion of the list is searched. This search method has a complexity of O(log n) as its complexity increases in the beginning of execution but decreases as the list gets narrowed down.

https://www.bigocheatsheet.com/

The Binary Search is the most efficient because its complexity is not affected by its input set as much as the linear search however, the list has to be sorted first.

 

The Fibonacci sequence

 


The Fibonacci sequence is a special set of numbers where 0 and 1 are the first numbers in the sequence and the next numbers are derived through adding the previous two as illustrated in the image above. Below are examples of functions that compute the sequence.

  • First we have a recursive function where the sequence is generated through calling through the function calling its self again. Through this we see how the function's complexity increases as the size of the input set grows and it thus has a complexity of O(2n).


  • Next we have a function using dynamic programming where each number in the sequence is stored in the array every time the function is called and what is returned is the number of  a certain index in the list. This illustrates a linear function as the complexity of the computation is directly proportional to the input. in other words to get the fifth number in the sequence 5 operations will occur to retrieve it and thus has a complexity of O(n).

https://www.bigocheatsheet.com/

We looking at the chart above again we see how O(n) is so much more efficient than O(2n) and the recursive method should be highly avoided as it produces functions that aren't very efficient making the better option the function using dynamic programming.

Hopefully this has helped you see the benefits in understanding the big O notation and have a basic understanding of how to implement it to your code. Through it we can produce an eye for quickly detecting algorithms that might reduce the efficiency of our code. 

Thank you for taking the time to read my blog happy coding <😉 />


References

Anon., 2019. What is the difference between Linear search and Binary search?. [Online]
Available at: https://stackoverflow.com/questions/700241/what-is-the-difference-between-linear-search-and-binary-search
[Accessed 11 June 2021].

Anon., n.d. Big 0. [Online]
Available at: http://web.mit.edu/16.070/www/lecture/big_o.pdf
[Accessed 11 June 2021].

Bell, R., 2009. A beginner's guide to Big O Notation. [Online]
Available at: https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation
[Accessed 11 June 2021].

Cake Labs, Inc, 2021. Big O Notation. [Online]
Available at: https://www.interviewcake.com/article/java/big-o-notation-time-and-space-complexity
[Accessed 11 June 2021].

Geeks For Geeks, 2021. Program for Fibonacci numbers. [Online]
Available at: https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
[Accessed 13 June 2021].

HyperionDev, 2021. Interview Preperation: Big O Notation, s.l.: s.n.

Ken, G., 2019. Which one is better, binary search or linear search?. [Online]
Available at: https://www.quora.com/Which-one-is-better-binary-search-or-linear-search
[Accessed 11 June 2021].

Rowell, E., n.d. Know Thy Complexities!. [Online]
Available at: https://www.bigocheatsheet.com/
[Accessed 15 June 2021].

 


Comments

Post a Comment