Vitalis

What is Computational Complexity and Big O?

What is computational complexity and Big O?

In a previous blog, I wrote about the two-pointer algorithm, but I didn’t dive into how efficient it is as the input size grows. Today, let’s explore how to measure the efficiency of an algorithm. Before revisiting the two-pointer algorithm, it’s important to understand computational complexity and Big O notation. (Check out the bloghere)

Prerequisites


To follow along, a basic understanding of algorithms and data structures is helpful.

Computational Complexity

What is it?
In simple terms, computational complexity is the amount of work needed to perform a specific task.

Imagine John pushing a wheelbarrow from Point A to Point B. The energy he uses gives us an idea of the work required. Computational complexity is similar, but instead of wheelbarrows, we’re measuring the resources a computer uses to perform a task.

You now grasp the idea, but for computational Complexity we are not moving wheelbarrows, let’s get to a deeper definition.

Computational complexity — it is the measure of the amount of computational resources(like time and memory) needed for a particular task.

We have now replaced work with more specific word computational resources.

If you quickly peep to your dictionary computational means relating to computer.

So this means we will use computer resources to perform a particular task.

I am keeping this simple so that we can get the understanding.
Computational complexity — It is the measure of the amount of the computational resources needed for a particular task

With this understanding we can go to the next definition.

Big-O

What is Big-O — in the simplest terms it is the measure of how efficient an algorithm is?

  • it Categorizes algorithm on how their time and space requirements grow as the input size grows

We have introduced Time and Space complexity, let’s take a step back and define the words introduced.

Time Complexity


-What is time complexity — it is how long it takes to run your function in computational steps.

We will talk about computational steps later, taking the example of John previously is how long John takes to take is wheelbarrow from point a to b.

Space complexity


-what is space complexity — it is the memory the function uses.

So we now know time complexity is the time taken to run the function in computational steps and space complexity is the memory used by the function

Let’s connects the dots.
Big O— Categorize algorithms on how their time and space requirements grows as the input size grows.

Replacing the terms we are categorizing algorithm on the time the algorithm takes to do a particular task and the memory it uses while doing the task.

One more thing, we are doing comparison,

So what is this comparison we are doing?
lets take a simple function taking in objects and doing a for in loop and returning each key and value

bash
const ages = {"mary":20, "peter": 30} function showAges(ages){
  for (const a in ages) { alert("name:", a, "ages:", ages[a]) }
} showAges(ages);

So that we do the comparison
1. We must understand that Big O is used in algorithm to represent the upper bound or what we can call the Worst case scenario.

To identify the worst case scenario we must do some comparison right?

E.g what if the ages where a million records how long would it take?? it’s a question we should answer.

And what i have just explain; is the last part of Big O definition (“INPUT SIZE GROWS”)

INPUT SIZE

It categorize algorithm as how their time and space requirements grow as theINPUT SIZEgrows

Now how do you calculate the Big O??

How to calculate BigO

  1. Split your algorithm into operations

  2. Calculate Big O for each operation

  3. Add up Big O from each operation

  4. Strip the constants

  5. Find the highest order term

Let’s take an example of the function we used

Step 1: Split your algorithm into operations

bash
// an operation const ages = {"mary":20, "peter": 30} function showAges(ages){
  //an operation for (const a in ages) { // an operation alert("name:", a, "ages:", ages[a]) }
} showAges(ages);

Step 2: Calculate Big O for each operation

bash
// an operation const ages = {"mary":20, "peter": 30} O(1) constant // let's assume i have an array here const mydummyarray = [1, 2, 3, 4] 0(1) // let's find half of it const halfofarray = mydummyarray.length/2 O(n/2) function showAges(ages){
  //an operation for (const a in ages) {
    O(n) linear // an operation alert("name:", a, "ages:", ages[a]) O(1)
  }
} showAges(ages);

i have added the array and calculating it’s half so that we can explain the aspect of stripping

Step 3: Add up the Big O from each operation

bash
O(1 + 1 + n/2 + n + 1)

Step 4: Strip the constants

bash
Stripping 1, 1/2 we remain with O(n)

Step 5: Find the Highest order term

bash
O(n)

What are O(1), O(n)

Let’s now talk about Big O functions.

Big O functions

We have


Constant — O(1)
Logarithmic O(Log n)
Linear O(n)
Log Linear O(n Log n)
Quadratic O(n²)
Cubic O(n³)
Exponential O(2^n)

For this blog i will explain the first two:

Constant O(1)

As the name suggest is something that does not change.
Lets quickly look at the properties of constant
1. The execution time is not dependent on input data.
2. The time complexity does not change.

Examples are

  1. Get (read an index e.g get index or an array array[1])

  2. Set (assigning e.g const age = 40 )

  3. Arithmetic operations (this are for example a+b)

  4. Comparison (e.g a===1)

Now we get

bash
// an operation const ages = {"mary":20, "peter": 30} O(1) constant // let's assume i have an array here const mydummyarray = [1, 2, 3, 4] 0(1)

On the above example notice we do set Ages to the set or mydummyarray to the array, which is constant O(1).

Logarithmic (O(Logn))

To understand it let’s look at it’s properties.

  1. The input data size reduces in each step

  2. You don’t need to look up all values

  3. The next action done will only be done on one of the possible elements

so let’s take an example
In binary search
We first get the length of the data.
Get the middle point
Set — our starting and ending point
Then check the value we are searching if its on the side of the starting to middle or from middle to the end,

With this you now understand first property which is — in each step the data input size reduces, — Because if the value we are searching is in between the first and the middle, we let go of the middle to the end, because our value can’t be there.

Second property as well is covered because we wont look up for the value in the other half.

And lastly the next action is only performed on one of the possible elements which is to look the first half or the second half.

Logarithmic is mostly used in divide and conquer approaches.

Wrapping Up

Understanding computational complexity and Big O is key to writing efficient code. Today, we covered:

What computational complexity is.
The basics of Big O notation.
How to calculate Big O.
Examples of common Big O functions like O(1) and O(log n).

In the next blog, we’ll dive deeper into other Big O functions

Let’s Connect!