Time complexity and space complexity in data structures and algorithms

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

Rendered by QuickLaTeX.com

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)

Rendered by QuickLaTeX.com

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

Rendered by QuickLaTeX.com

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

Rendered by QuickLaTeX.com

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

Rendered by QuickLaTeX.com

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

O(1) is ideal (constant – no loops)
O(log x) is good (logarithmic)
O(x) is fair (linear- for loops, while loops)
O(x logx) is bad (log-linear)
O(x^2), O(2^x), and O(x!) are the worst

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(n^2) and space complexity O(n^2) space

What causes a space complexity in a function?

  1. Variables
  2. Data structures
  3. Function call
  4. 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

Rendered by QuickLaTeX.com

#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

Rendered by QuickLaTeX.com

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

Rendered by QuickLaTeX.com

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(n^2)

As we said, we should neglect the constants but what if we have an expression like this O(n^2 +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

Rendered by QuickLaTeX.com

Consider some examples

  • O(n^2+n^2)  gives  O(n^2)
  • O(n+log n) gives O(n)
  • O(n^2 +n) gives O(n^2)
  • O(5*2^n+100n^{200}) gives O(2^n)

Note: the expression O(A^2+B) 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(n^2)

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

Rendered by QuickLaTeX.com

Rendered by QuickLaTeX.com

Rendered by QuickLaTeX.com

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?

Rendered by QuickLaTeX.com

 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)

Rendered by QuickLaTeX.com

With every iteration in linear loops you can ADD or SUB

Logarithmic loops

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

Rendered by QuickLaTeX.com

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(n^2)

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(n^3)

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(n^2)

O(n+n^2)

Use the rule #3

BIG O(n^2)

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(n^2) 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+n^2)

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 n^2 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(n^2+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 n^2 increases most rapidly than any other term in the BIG O

So, we can write BIG O(n^2) 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

Mohammed Anees

Hey there, welcome to aneescraftsmanship I am Mohammed Anees an independent developer/blogger. I like to share and discuss the craft with others plus the things which I have learned because I believe that through discussion and sharing a new world opens up

Leave a Reply

Your email address will not be published.