Scribd
Upload
2 views3 pages

Time Complexity All Examples

The document provides examples of various time complexities in algorithms, including constant time (O(1)), logarithmic time (O(log n)), linear time (O(n)), n log n time (O(n log n)), quadratic time (O(n²)), cubic time (O(n³)), polynomial time (O(n^k)), and exponential time (O(2^n)). Each example includes code snippets and a step-by-step explanation of the operations leading to the respective time complexities. This serves as a reference for understanding how different algorithmic approaches affect performance based on their time complexity.

Uploaded by

prasamsaevangaly7
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views3 pages

Time Complexity All Examples

The document provides examples of various time complexities in algorithms, including constant time (O(1)), logarithmic time (O(log n)), linear time (O(n)), n log n time (O(n log n)), quadratic time (O(n²)), cubic time (O(n³)), polynomial time (O(n^k)), and exponential time (O(2^n)). Each example includes code snippets and a step-by-step explanation of the operations leading to the respective time complexities. This serves as a reference for understanding how different algorithmic approaches affect performance based on their time complexity.

Uploaded by

prasamsaevangaly7
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Time Complexity Examples (Step-by-Step)

Constant Time – O(1)


Code:
int getFirst(int arr[])
{
return arr[0];
}

Steps:
• One array access
• One return statement

Time Complexity: O(1)

Logarithmic Time – O(log n)


Code:
int binarySearch(int arr[], int n, int key)
{
int low = 0, high = n - 1;
while(low <= high)
{
int mid = (low + high) / 2;
if(arr[mid] == key)
return mid;
else if(arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}

Steps:
• Array size reduces to half each iteration
• n → n/2 → n/4 → ...

Time Complexity: O(log n)


Linear Time – O(n)
Code:
int sum(int arr[], int n)
{
int s = 0;
for(int i = 0; i < n; i++)
s = s + arr[i];
return s;
}

Steps:
• Loop runs n times
• Constant work per iteration

Time Complexity: O(n)

n log n Time – O(n log n)


Example: Merge Sort (Concept)

Steps:
• Dividing array → log n levels
• Merging at each level → n operations

Time Complexity: O(n log n)

Quadratic Time – O(n²)


Code:
void printPairs(int n)
{
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
printf("%d %d", i, j);
}

Steps:
• Outer loop runs n times
• Inner loop runs n times

Time Complexity: O(n²)


Cubic Time – O(n³)
Code:
void tripleLoop(int n)
{
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
printf("%d %d %d", i, j, k);
}

Steps:
• Three nested loops
• Each loop runs n times

Time Complexity: O(n³)

Polynomial Time – O(n^k)


Explanation:
• k nested loops
• Each loop runs n times

Time Complexity: O(n^k)

Exponential Time – O(2^n)


Code:
int fib(int n)
{
if(n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}

Steps:
• Each call makes two recursive calls
• Number of calls doubles

Time Complexity: O(2^n)

You might also like