Demystifying Time Complexity & Big O Notation

What is Time Complexity?

Why do we need to understand Time Complexity?

How to compare the time complexity of an algorithm?

int n=10, sum = 0;
for(int i=1; i<=n; i++)
{
sum = sum + i;
}
System.out.println(sum);
int n=10;
System.out.println((n*(n+1))/2);

What is Big O?

Understanding O(1)

int b = {1,2,3,4,5}
System.out.println(b[0]);

Understanding O(n)

int a = 0, n[] = {1,2,3,4,5};
for(int i = 0; i <n.length; i++)
{
if(n[i]==a)
{
System.out.println("Found");
break;
}
}

Understanding O(logn)

int arr[] = {10,20,30,40,50}; 
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;

Understanding O(n2)

for(int i = 1; i<=5; i++)
{
for(int j = 1; j<=i; j++)
{
System.out.print(j);
}
System.out.println();
}

Understanding O(2n)

void solve_hanoi(int N, string from_peg, string to_peg, string spare_peg)
{
if (N<1) {
return;
}
if (N>1) {
solve_hanoi(N-1, from_peg, spare_peg, to_peg);
}
print "move from " + from_peg + " to " + to_peg;
if (N>1) {
solve_hanoi(N-1, spare_peg, to_peg, from_peg);
}
}

Understanding O(n!)

const nFacRuntimeFunc = (n) => {
for(let i=0; i<n; i++) {
nFacRuntimeFunc(n-1);
}
}

Let’s Recap:

  • O(1) — Constant time complexity (Best🎯)
  • O(n) — Linear time complexity
  • O(log n) — Logarithmic time complexity
  • O(n2) — Quadratic time complexity
  • O(2n) — Exponential time complexity
  • O(n!) — Factorial time complexity (Worst😭)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sai Ashish Konchada

Sai Ashish Konchada

28 Followers

Full Stack Developer 👨🏻‍💻| Google DSC Lead 21 🧑🏻‍🎓 | AIR 102 India’s Super Brain 🧠| Top 50 Technical Blogger ✍🏻