Blog / Data Structures & Algorithms
Time Complexities (Part 1)
  • Nov 18, 2020
  • 96
  • 75

When we talk about Big O and scalability of code, we simply mean when we grow bigger and bigger with our input, how much does the algorithm or function slow down? In this post, we will understand more about Big O, time complexity, and why we need to be concerned about it when developing algorithms.


Advertisement
 


1. Computational Complexity

In computer science, computational complexity is a field which analyzes algorithms by calculated the amount resources required to execute it. The amount of resources varies based on the size of the input. So, we can understand the complexity is a function of n, where n is the size of the input.

The complexity analysis includes time complexity and space complexity. We will discuss space complexity in the next post while this post will mainly focus on time complexity and how to calculate it from different algorithms.

2. Time Complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.
When analyzing time complexity of an algorithms, there are 3 scenarios that you must consider:
  • Best-case: this is the complexity of solving the problem for the best input.
  • Average-case: this is the average complexity of solving the problem. This complexity is defined with respect to the distribution of the values in the input data.
  • Worst-case: this is the complexity of solving the problem for the worst input of size n.

For example: let's consider the catching Pikachu function that we discussed in the previous post:

const pokemon = ['Pikachu', 'Meowth', 'Bulbasaur'];
  
function catchPikachu (array) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === 'Pikachu') {
       console.log('Catch Pikachu!'); return;
    }
  }
}
  
catchPikachu(pokemon);

Consider the input, we have Pikachu is the first element of the pokemon array. The function just needs to iterate to the first element and finishes so it would be a best-case. However, if we are looking for Meowth instead of Pikachu, it would be an average-case. And finally, if we need to catch a Bulbasaur, it would be the worst-case.


3. Big O Notations and Time Complexities

If you have read my previous post, you may understand to some extend regarding Big O Notation. Below is the definition:

Big O notation, sometimes called “asymptotic notation”, is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

In computer science, Big-O notation is used to classify algorithms according to how their running time or space requirements grow as the input size (n) grows. This notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.

Let’s see some common time complexities described in the Big-O notation.


NameTime Complexity
Constant TimeO(1)
Logarithmic TimeO(logn)
Linear TimeO(n)
Quasilinear TimeO(nlogn)
Quadratic TimeO(n^2)
Exponential TimeO(2^n)
Factorial TimeO(n!)

We have discussed more about Big O notation and Time Complexity when analyzing algorithms. We will focus more in details of each Time Complexity mentioned above in the next post. Thank you for reading my post, see you next time!

Read more in this series:


Using cherry-pick to select specific commits for your Pull Request.1. Create a new branch based on the target of the Pull Requestgit branch cherry-branch origin/master2. Switch to a new branchgit chec ...

After deployment Angular and API on IIS, it's working fine unless I refresh the page. Once refreshed, the web encountered 404 error. In this article, I will explain how to resolve this.Since Angular i ...

There are some benefits of keeping both UI and API parts in the same place for small projects. In this article, I will explain how I did to deploy Angular Web and ASP .Net Core API in the same folder ...

I got CORS error after publishing my API and Angular app to IIS even though CORS is enabled and the origins of the Angular app is added. Below is how I resolved this issue.Just simple, make sure you s ...

In Object-Oriented Programming, S.O.L.I.D refers to the first five design principle for the purpose of making software designs more understandable, flexible, and maintainable. The principles was first ...

1. The Situation:Error Message:&nbsp;Pulse Secure Application failed to load Java. Please install correct JRE version.Description: This issue happens when I'm using a M1 Mac with a correct version of ...

Accelerated Mobile Pages (AMP)&nbsp;focuses on delivering static content from publishers as quickly as possible and possibly rewards early adopters with a boost in rank. Let's see how to implement it ...

Below is how to decrypt/convert a Hex string value into text using VB.Net:Decrypting Hex string value to string in VB.Net Function HexToString(ByVal hex As String) As String Dim text As New Sy ...

After a month of publishing on Google Play, Jungle Words has made it to the Top Android Games To Try Out In April 2021. Please check it out!&nbsp;GameKeys.netGameKeys is a website which introduces gam ...