Do you know? What is **Time complexity and space complexity** in data structures and algorithms? Let me explain to you what do we mean by time complexity and space complexity

For analyzing an algorithm we usually use two parameters know as time and space to measure the efficiency of an algorithm

As we know, as human beings, time and space are the scariest resources that we have

So, we should use it wisely to produce efficient results with speed

For example: Suppose you are given the task of transferring media files to some other country

**What will you do?**

You might say, you will transfer it through the internet but the problem is that the file is large (20TB) terabytes and you have internet with a bandwidth (transfer rate of 1000 Mbps)

How much time will it take to transfer through the internet?

It will take 2days and 52 minutes, 2 seconds

If it is urgent and you don’t mind cost then it would be better to transfer files through aircraft

So, that it will be delivered within a few hours to the desired destination

**To sum up**: big O notation is a way to describe the algorithmic complexity of a function for a given n amount of input

**Time complexity** means if the time to run the function increases then it is called time complexity

**Space complexity** means if the memory to run the function increases then it is called space complexity

#### How to describe the runtime of an algorithm

We can describe the runtime of an algorithm by using a big O OR asymptotic notations

Remember Big O is an equation that describes how time changes to certain input

**For internet transfer**: we can describe the runtime of a data transfer algorithm as **O(s)** where ‘s’ is the size of the media file

the time to transfer media file increases linearly with the size of the file

**for aircraft transfer**: we can describe the runtime of a data transfer algorithm as **O(1)** because the time will remain constant no matter how much the size increase

**Note**: you should not have to use O(n) in every equation that, you write, instead you can use other variables such as O(s)

```
for (int i=0;i<b;;i++)
{
sum +=a;
}
```

**For example**, for the loop shown above, we can write runtime of it as **O(b)** instead of O(n)

Always the linear will surpass the constant at some point even the constant so big or how slow might the linear growth

#### Why we use time and space complexity

- Time and space complexity gives you an estimation so, that you won’t get shocked when the result is produced
- It produces a choice to select one of the two ways of doing something
- You will know, which part of the code should be optimized to utilize the resources efficiently

#### How to express time and space complexity

We can express time and space complexity by using a function called f(n)

Where n is the size of the input

The function f(n) is expressed by using the big O notation

With time and space complexity, we want to predict the complexity of the algorithm as input size increases

The below graph show’s the rate of growth of some famous big O times

So, that means O(1) has the least complexity while O(x!) has the highest complexity

#### Space complexity

Space complexity means the space or memory which is required by the algorithm to run efficiently

The space complexity is a parallel concept to time complexity

For example: to iterate an array from 0 to n it will take time complexity **O(n)** and space complexity **O(n)** space

For two dimensional array such as a matrix of order nxn it will take time complexity of **O()** and space complexity ** O()** space

#### What causes a space complexity in a function?

- Variables
- Data structures
- Function call
- Memory allocations

#### Some basics rules of big O

#### #Rule 1: Add different statements runtime

To find the runtime of a code snippet we should add all the statements runtime

#### #Rule 2:Neglect the constant

Consider the two code snippet mentioned below for finding the min and max element in an array

The first code snipped contain two loops for doing the same work as the second code snipped

The Second code snipped contain only one loop with two instruction to the same job as first code snipped

So, what do you think? which code snipped will run faster?

Do you know? Both the code snippets will take the same time to run the code

**Why?**

Always remember you should neglect the constant for finding the run time of the algorithm

You might say the first code snipped contain two loops so, it will take run time as O(n)+O(n)=O(2n)

No!, it won’t!

we neglect the constant and write O(n) instead of O(2n) also don’t think that by writing O(2n) you are more precise

No!, you are not!

#### #Rule 3:Neglect the non-dominant terms

Let us consider, a code snippet as mentioned below

The first part of the code is to find a max element in an array which take O(n) run times

The second part of the code is to iterate an arrays by a and b and print all the elements O()

As we said, we should neglect the constants but what if we have an expression like this O( +n), then here n is not exactly a constant

What will you do?

You should also neglect the non-dominant terms in a big O expression

When it comes to big O notation, we usually care about significant terms that have the most impact, and also, remember, as the input grows larger then at that instant only the fastest growing terms matter most than constants

Consider some examples

- O() gives O()

- O(n+log n) gives O(n)

- O() gives O()

- O() gives O()

**Note:** the expression O() cannot be reduced until you have some specific knowledge about it

#### #Rule 4: different inputs gives different variables

Consider the two code snippets first and second as mentioned below

Most people would get confused here, at this instant, they would say both, they find codes snipped are similar so, therefore it is O()

No, it is not!

**Remember** when n is the size of the array, if the code snipped have two different arrays then it does not mean the length of the entire array

#### Constant time

Suppose, we are having a simple C program to print Hi there! Then how time will it take to execute the print statement, it will take constant time to execute the print statement

The constant time does not depend on the input size

#include <stdio.h> int main() { printf("Hi there!\n"); return 0; }

The above program is having **O(1)**

Where O is called “order of”

#### Linear loops (Single loop)

Suppose, we have an Array of size 10 and we would like to iterate all the elements of a given array, then, in that case, how much time will it take to iterate all the elements of an Array?

for(i=0;i<9;i++) { printf("%d\n",arr[i]); }

It usually, depends upon, how many elements are there in an array suppose, if we have n elements in an array then, in that case, the time taken will be **O(n)**

for(i=0;i<9;i+=2) { printf("%d\n",arr[i]); }

On the other hand, if we iterate half of the loop then at that instant, the time taken will be **O(n/2)**

With every iteration in linear loops you can ADD or SUB

#### Logarithmic loops

With every iteration in Logarithmic loops, you can Divide or Multiply

**Case 1**

for(i=1;i<9;i=i*2) { printf("%d\n",arr[i]); }

**Case 2**

for(i=9;i>=1;i=i/2) { printf("%d\n",arr[i]); }

The time taken by logarithmic loops will be **O(log n)**

#### Nested loops

A loop that contains loops inside it, is called a nested loop

#### Linear logarithmic loops

for(i=0;i<10;i++) for(j=1;j<10;j*=2) { statements; }

Every iteration of the inner loop is multiplied by 2

The time taken by linear logarithmic loops to executed the statements is given as **O(n log n)**

#### Quadratic loop

In a quadratic loop, every iteration of the outer loop is equal to every iteration of the inner loop

for(i=0;i<10;i++) for(j=0;j<10;j++) { statements; }

The time taken by the quadratic loop is given by **O()**

#### Dependent quadratic loop

In a dependent quadratic loop, the inner loop will be dependent on the outer loop

for(i=0;i<10;i++) for(j=0;j<=1;j++) { statements }

The time taken by the dependent quadratic is given by **O(n+1)/2**

#### Cubic loop

**Case 1**

for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j = j + +) for(int k = 0; k < 10; k = k + +) { statements; }

**Case 2**

for(int i = 0; i < 10; i++) for(int j = 0; j < 10 + 5; j = j + 2) for(int k = 0; k < 10; k = k + 3) { statements; }

The time taken by the three loops will be given by **O()**

#### O(n!)

Let’s talk about a big O that you won’t likely encounter in case, if you are writing some code and you have O(n!) complexity then that means you are doing something wrong

You probably won’t encounter it but it exists

void nFacRuntimeFunc(int n){ for(int i=0; i<n; i++){ nFacRuntimeFunc(n-1); } }

**Array sorting Algorithms**

#### Some BIG O calculation examples

To do some BIG O calculations let’s use some JavaScript examples as mentioned below

Suppose, we have a function called one that has two statements that are of O(1) and, O (1), and also a loop that contains another function called two that is outside the function one

As we know, always a for loop will be linear, so, O(n) while, the function called two is dependent upon the input size so, O(n)

Next, consider a random statement (**let stranger =true;**)that will get executed as many times as the input size so, O(n) then the statement **a++;** is also in the loop so, O(n)

function one(input) { let a=10; //O(1) a=60+33; // O(1) for(let i=0; i<input.length; i++){ //O(n) functiontwo(); //O(n) let stranger =true; //O(n) a++; //O(n) } return a; // O(1) } one() //function call

O(1)+ O(1)+ O(1)+ O(n)+ O(n)+ O(n)+ O(n)

3+4n

BIG O(3+4n) =n

So, BIG O(n)

function one(input){ let a=20; //O(1) let b=75; //O(1) for(let i=0; i < input; i++){ let x=i+2; //O(n) let y=i+4; //O(n) let z=i+2; //O(n) } for(let j=0; j<input; j++){ let c= j*2; //O(n) let d= j*3; //O(n) } let status ="random"; //O(1) }

BIG O(3+5n)=n

So, BIG O(n)

function sketch(items){ console.log(item[0]); var middleIndex =Math.floor(items.length/2); var index =0; while (index< middleIndex){ console.log(items[index]); index++; } for (var i=0; i< 100; i++){ console.log('hi'); } }

The above function sketch first, print the first item in the array so, O(1) then, print half of the array items by using a while loop so, O(n/2) next, we are not looping all the items in the array but instead, we loop only 100 items by using a for loop

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

O(1+n/2+100)

O(n/2+100)

BIG O(n)

function printAllNumbersThenAllPairSums(numbers) { console.log('these are the numbers:'); numbers.forEach(function(number) { //O(n) console.log(number); }); console.log('and these are their sums:'); numbers.forEach(function(firstNumber) { //O(n) numbers.forEach(function(secondNumber) { //O(n) console.log(firstNumber + secondNumber); }); }); } printAllNumbersThenAllPairSums([1,2,3,4,5])

O(n)+O(n) X O(n)

O(n)+O()

O(n+)

Use the rule #3

BIG O()

Let us suppose, we have a function called print all numbers then all pair sums

In the first part of the code, print all the numbers in an array that is of O(n)

The second part of the code, contains two for loops that are of O() also it add the numbers in an array in serial order such as [1+1, 2+1, 3+1, 4+1, 5+1][2+1, 2+2, 3+2, 4+2, 5+2].. etc.

The big O notation of the function called print all numbers then all pair sums is O(n+)

The purpose of the rule#3 is to neglect the non dominant terms which mean we care only about the most important term, in this case, we neglect the O(n)

**Why?**

Because as the input increases the size of the is more important than O(n)

So, that means we always keep the most dominant term

Let’s see, another example to make the rule #3 clear

Suppose, we have a BIG O(+5n+200+n/2)

Next, how do we simplify the above BIG O by using rule #3?

As we know, the rule#3 says we only worry about the most dominant term because the term increases most rapidly than any other term in the BIG O

So, we can write BIG O() by dropping the all non- dominant terms

#### Some space complexity examples

Let’s suppose, we have a function called Demo that prints out “hi there” 5 times then the time complexity of that function will be O(n) and space complexity will be O(1)

Why the space complexity is O(1) here?

Because The only thing the demo function is doing is creating a variable called let i=0;

That’s it! We are not adding any additional items to the memory

function demo(n) { for (let i = 0; i < n; i++) { //O(1) space and //O(n) Time console.log('hi there'); } } demo(5); // function call with parameter

Let’s consider another simple function called Demo that prints “hi” 6 times then the time complexity will be O(n) and space complexity will be O(n)

Why the space complexity is O(n) here?

Because we created an array and fill it with the item “hi” and we also created a variable but as per our big O rule #2 we neglect the constants so, it will be O(n)

function Demo(n) { var array = []; //O(n) space for (let i = 0; i < n; i++) { // O(n) Time array[i] = 'hi'; } console.log( array); } Demo(6) //function call

## Leave a Reply