Big O Notation Basics for Web Developers

 What is Big O Notation?

Big O Notation, also known as Landau's symbol, is a language used for communicating or describing how effective a function or algorithm is and refers to its rate of growth. There are seven main functions in Big O Notation such as constant, linear, quadratic, exponential and more. For example, constant functions will remain as effective and fast regardless of the size of input. Then one gets exponential functions which grow dramatically as the size of the input grows. Each input is compounded and as such efficiency decreases. 

When it comes to software development it is not just about writing code that works, but also about writing clean, effective and efficient code. It is essential for developers to understand Big O Notation as it can assist with understanding how your algorithms will scale in real world application and how long it will take you to handle those requests to make the best application for your end users. 

What is a Quadratic Function?

A Quadratic function (or Quadratic Time Complexity) is an algorithm that is directly proportional to the squared size of the nth term. The complexity will increase and efficiently and speed will decrease in proportion to the increase of the squared nth term.

                                                                                                             (Salem, 2017)

Take this nested loop for example. The for loop searches through the array at minimum once and then the if statement loops through the array again. Say you have a deck of cards, you would loop through the deck and removing all the duplicates along the way. You would continue doing this until you reach the end of the deck. The more cards you have in a deck the longer the algorithm will take to execute and the more the efficiency decreases.

Linear vs Binary Search Algorithms?

A linear search (0(n)) looks through a list or array sequentially one at a time and will not jump to any values. The larger the list, the longer it takes to search to execute. Take a look at the below example, a linear search scans through each element one by one until it finds the element "J".

                                                                                                                       (Geeks for Geeks, 2021)

A binary search (O(log(n)) finds the middle of a list and determines whether the element we are looking for is more or less than the value we are at, and continues to do this to the sublists until it finds the element you are searching for. Take a look at the below example, the binary search scans goes to the middle element of the list, determines if "J" is greater or less than "L", then goes to the middle point of the sublist and so forth until it locates the element we are searching for which is "J". 

                                                                                                 (Geeks for Geeks, 2021)

If you have a very small list of data, either linear or binary search is fine to use and both can be efficient, but the larger your list get the more efficient binary search becomes over linear search. If you are looking for number 723 out of a list of 1500, to use a linear search to sequentially go through each element one by one is far from efficient. Binary would be the better choice as it can jump through the list and cut search time nearly in half. 

Fibonacci Sequence?

The Fibonacci Sequence is a series of numbers. Each number in the sequence is the sum of the two preceding numbers. The two origin values are 0 and 1. The are a number of ways to find the numbers in the Fibonacci sequence, two will be shown here. The first is the recursive function:

                                                                                                                        (Manson, 2021)

The second is a non-recursive function:

                                                                                                                          (Manson, 2021)

In Big O Notation, the recursive Fibonacci function is an 'exponential' and the non-recursive Fibonacci function is 'constant'. The more effective algorithm is the 'constant' one as the 'exponential' algorithm does a lot of repeated work. The non-recursive function cuts out the unnecessary repetition and stores just the previous two numbers to determine the next. 

Sources:

Choudhary, V., 2021. Big-O Notation Explained with Examples. [online] Developer Insider. Available at: <https://developerinsider.co/big-o-notation-explained-with-examples/> [Accessed 27 September 2021].

Gamblin, T., 2010. What is the big deal about Big-O notation in computer science?. [online] Stack Overflow. Available at: <https://stackoverflow.com/questions/1996457/what-is-the-big-deal-about-big-o-notation-in-computer-science> [Accessed 27 September 2021].

GeeksforGeeks. 2021. Linear Search vs Binary Search - GeeksforGeeks. [online] Available at: <https://www.geeksforgeeks.org/linear-search-vs-binary-search/> [Accessed 27 September 2021].

GeeksforGeeks. 2021. Program for Fibonacci numbers - GeeksforGeeks. [online] Available at: <https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/> [Accessed 27 September 2021].

Interview Cake: Programming Interview Questions and Tips. 2021. Big O Notation | Interview Cake. [online] Available at: <https://www.interviewcake.com/article/java/big-o-notation-time-and-space-complexity> [Accessed 27 September 2021].

n.d. Big O Notation. [ebook] MIT, p.2. Available at: <http://web.mit.edu/16.070/www/lecture/big_o.pdf> [Accessed 27 September 2021].

Salem, A., 2017. An Easy-To-Use Guide to Big-O Time Complexity. [online] Medium. Available at: <https://medium.com/@ariel.salem1989/an-easy-to-use-guide-to-big-o-time-complexity-5dcf4be8a444> [Accessed 27 September 2021].

Skeet, J., 2009. What is the difference between Linear search and Binary search?. [online] Stack Overflow. Available at: <https://stackoverflow.com/questions/700241/what-is-the-difference-between-linear-search-and-binary-search> [Accessed 27 September 2021].