Description:

Efficient algorithms are the backbone of great software development. This blog dives into the basics of time and space complexity, helping you analyze and optimize your code. Learn about Big O notation, common complexity classes, and how to evaluate the performance of your programs through practical examples and easy-to-follow explanations. Whether you're preparing for interviews or aiming to excel in coding challenges, this guide will enhance your problem-solving skills and understanding of algorithmic efficiency.

here we will talk about 2 topics they are :→

a>Time Complexity :→

“time complexity” doesn’t mean time to run.

because diff machine have diff type of specification.

Like there a highend device so it will take less time to execute the code. and vice-versa for lowend device.

so what’s time complexity ?

Basically, the time complexity of a particular code depends on the given input size, not on the machine used to run the code.

here is the pictorial representation to understand “time complexity“ :→

now the question is :

how we represent the time complexity of code ?

it’s represented by “ O(time_taken) ”. It’s named as “Big O notation”

here let’s the time complexity example :→

#include <bits/stdc++.h>
using namespace std;

int main()
{
  for (int i = 1; i <= 5; i++)
  {
    cout << i<<" ";
  } 
}

time complexity of this code is :→

O(5×3) = O(15)

for loop will run ( 1 to 5 ) and has three(that will only run) step that’s important in this programme.

now if we consider 5 as n to generalize it … now the time complexity of a “for loop is O(N) that going from 1 to n and printing a data“.

P.T.R( for time com.) :→

1>we always have to find “time complexity” we have to take the “worst case”.

2>we can avoid the constant terms.

3>we can avoid the smaller terms.

now lets see what’s the worst case :→

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int marks;
  cin >> marks;
  if (marks<25)
  {
    //if marks=15 {baest case}
    cout << "barely passed";
  }
  else if(marks<45){
    cout << "grade:B";
  }
  else if(marks<65){
    cout << "grade:C";
  }
  else{
    //marks=95 (all part of code will run that's the  worst case)
    cout << "grade:A";
  }
}

now let’s see some example to understand it in more better manner :→

Q1>

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int b = 2;
  for (int i = 0; i < 4; i++)
  {
    cout << "raj"<<" ";
  }
}

O(3N+1)=> O(3N)+O(1)=>O(3N)=>O(N)

3*N=> 3 number of important steps and 1 is for constant . but for time complexity we gonna ignore the constant value

Q2> find t.c of this code :→

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int n;
  for (int i = 1; i <= n;i++){
        for (int j = 1; j <= n;j++)
  }
}

here i=1> j=1 to n [n steps]

i=2=>j=1 to n

…. i=n => j = 1 to n

let’s add all N+N+N…….n times :→ N²

so the t.c. of the code is :→ O(N²)

Q3> find the tc. :→

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int n;
  for (int i = 1; i <= n;i++)
  {
     for (int j = 1; j <= i;j++)
  }
}

for i=1 => j =1 [1 step]

i=2 => j=1,2 [2 steps]

i=3 => j=1,2,3 [3steps]

… i=n =>j=1…..n [n steps]

total steps :→ 1+2+3…+n=n(n+1)/2=n²/2+n/2

n/2 small compared to n²/2 so we will ommit that.

so, O(N²) is t.c. for this.

and here we gonna end basics of tc and move on to “space complexity”,

b>Space Compelxity :→

Space complexity generally represents the summation of auxiliary space and the input space.

Auxiliary space refers to the space that we use additionally to solve a problem. And input space refers to the space that we use to store the inputs.

here the s.c is :→ O(3) samelt if we replace “3“ with “N“ so the sc will be O(N).

that’s all we have to know bout space and time complexity.

Conclusion

Time and space complexity are fundamental pillars of algorithm analysis, guiding developers in crafting efficient and scalable solutions. Time complexity evaluates the runtime of an algorithm as the input size grows, ensuring that solutions remain practical for large datasets. Space complexity assesses the memory usage, highlighting how efficiently an algorithm utilizes system resources.

By understanding and balancing these complexities, developers can make informed decisions, optimizing both performance and resource usage. Mastery of these concepts is essential for designing algorithms that are not only correct but also efficient, adaptable, and capable of meeting the demands of real-world applications.

let’s meet you at the next section.

signing off for now.

-by The_OS_coder(I’M BAtman🦇)

Big OOPS to Big O: Simplifying Complexity! 🚀

Table of contents