Coding N Concepts
Basics of Time Complexity
Page content
In this tutorial, we’ll learn how to calculate time complexity of a function execution with examples.
Time Complexity
Time complexity is generally represented by big-oh notation 𝘖.
If time complexity of a function is 𝘖(n), that means function will take n unit of time to execute.
These are the general types of time complexity which you come across after the calculation:-
| Type | Name |
|---|---|
| 𝘖 (1) | Constant |
| 𝘖 (log₂n) | Logarithmic |
| 𝘖 (√n | Root |
| 𝘖 (n) | Linear |
| 𝘖 (n²) | Quadratic |
| 𝘖 (n³) | Cubic |
| 𝘖 (2ⁿ) | Exponential |
| 𝘖 (nⁿ) | Exponential |
Time Complexity in the increasing order of their value:-
1 < log₂n < √n < n < nlog₂n < n² < n³ ... < 2ⁿ < 3ⁿ ... < nⁿ
Time Complexity Calculation
We are going to understand time complexity with loads of examples:-
for loop
Let’s look at the time complexity of for loop with many examples, which are easier to calculate:-
Example 1
for(int i=0; i<n; i++){}
loop run `n` times
hence Time Complexity = 𝘖(n)
Example 2
for(int i=0; i<n; i=i+2){}
loop run `n/2` times which is still linear
hence Time Complexity = 𝘖(n)
Example 3
for(int i=n; i>1; i--){}
loop run `n` times
hence Time Complexity = 𝘖(n)
Example 4
for(int i=1; i<n; i++){}
for(int j=1; j<n; j++){}
two individual loops run `n+n = 2n` times which is still linear
hence Time Complexity = 𝘖(n)
Example 5
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){}
}
Nested loop run `nxn = n²` times which is non-linear
hence Time Complexity = 𝘖(n²)
Example 6
for(int i=1; i<n; i=i*2){}
Calculation:
――――――――――――――――――――――――――――
values of `i` in `for` loop
――――――――――――――――――――――――――――
1
2
2²
2³
.
.
2ᵏ
――――――――――――――――――――――――――――
The loop will terminate when:-
i ≥ n
2ᵏ ≥ n
k ≥ log₂(n)
so log₂(n) is total unit of time taken by the loop
hence Time complexity = 𝘖(log₂(n))
Example 7
for(int i=1; i<n; i=i*3){}
Calculation:
Similar to the last example,
value of `i` in `for` loop is i = 3ᵏ
The loop will terminate when:-
i ≥ n
3ᵏ ≥ n
k ≥ log₃n
so log₃n is total unit of time taken by the loop
hence Time complexity = 𝘖(log₃n)
Example 8
for(int i=n; i>1; i=i/2){}
Calculation:
――――――――――――――――――――――――――――
values of `i` in `for` loop
――――――――――――――――――――――――――――
n
n/2
n/2²
n/2³
.
.
n/2ᵏ
――――――――――――――――――――――――――――
The loop will terminate when:-
i ⋜ 1
n/2ᵏ ⋜ 1
2ᵏ ≥ n
k ≥ log₂(n)
so log₂(n) is total unit of time taken by the loop
hence Time complexity = 𝘖(log₂(n))
Example 9
for(int i=0; i<n; i++){
for(int j=1; j<n; j=j*2){}
}
Calculation:
outer loop complexity = 𝘖(n)
inner loop complexity = 𝘖(log₂(n))
hence Time complexity = 𝘖(nlog₂(n))
Example 10
int p = 0;
for(int i=1; p<=n; i++){
p = p + i;
}
Calculation:
value of `i` and `p` in `for` loop:-
―――――――――――――――――――
i p
―――――――――――――――――――
1 0+1=1
2 1+2=3
3 1+2+3=4
4 1+2+3+4
. .
. .
k 1+2+3+4+...+k
k k(k+1)/2
―――――――――――――――――――
The loop will terminate when:-
p > n
k(k+1)/2 > n
k² > n
k > √n
so √n is total unit of time taken by the loop
hence Time complexity = 𝘖(√n)
Example 11
int p = 0;
for(int i=1; i<n; i=i*2){
p++;
}
for(int j=1; j<p; j=j*2){
// statement
}
Calculation:
1. first `for` loop will take log₂(n) unit of time to execute.
At the end of first loop value of p = log₂(n)
2. second `for` loop will take log₂(p) unit of time to execute.
hence Time Complexity = 𝘖(log₂(p)) = 𝘖(log₂log₂(n))
while loop
If you understand how to calculate the time complexity of for loop then while loop is piece of cake.
Example 1
int i=1;
while(i<n){
//statement
i=i*2;
}
Time Complexity = 𝘖(log₂(n))
Example 2
int i=n;
while(i>1){
//statement
i=i/2;
}
Time Complexity = 𝘖(log₂(n))
Example 3
int i=1;
int k=1;
while(k<n){
//statement
k=k+i;
i++;
}
Time Complexity = 𝘖(√n)
Variable Time Complexity
It is not necessary that function always take fixed unit of time to execute, sometime it depends on the input parameters. Here are some examples where time complexity is not fixed:-
Example 1
method(n, m){
while(n!=m){
if(n>m){
n = n-m;
}else{
m = m-n;
}
}
}
best case time = 𝘖(1)
(when n = m)
worst case time = 𝘖(n)
(when n is very larger then m (e.g. n=16, m=1))
Example 2
method(n){
if(n<5){
//statement
}else{
for(i=0;i<n;i++){
//statement
}
}
}
best case time = 𝘖(1)
(when n < 5)
worst case time = 𝘖(n)
(when n ≥ 5)
Recursive Functions
Let’s see the time complexity of recurring (or recursive) functions:-
Example 1
test(int n){
if(n>0){
//statement
test(n-1);
}
}
// T(n) = T(n-1) + 1 = 𝘖(n)
Calculation:
Base case
T(0) = 1
Time taken by nth task is time taken by (n-1)th task plus 1
T(n) = T(n-1) + 1 --(1)
Similarly time taken by (n-1)th task is (n-2)th task plus 1
T(n-1) = T(n-2) + 1 --(2)
T(n-2) = T(n-3) + 1 --(3)
T(n) = T(n-3) + 3 --after substituting (2),(3) in (1)
T(n) = T(n-k) + n
...
Assume (n-k)th is 0th task means n=k
T(n) = T(0) + n
T(n) = 1 + n ⋍ n
hence Time Complexity = 𝘖(n)
Example 2
test(int n){
if(n>0){
for(int i=0; i<n; i++){
//statement
}
test(n-1);
}
}
// T(n) = T(n-1) + n = 𝘖(n²)
Calculation:
Base case
T(0) = 1
Time taken by nth task:-
T(n) = T(n-1) + n
T(n-1) = T(n-2) + n-1
T(n-2) = T(n-3) + n-2
..
..
T(n) = T(n-3) + (n-2) + (n-1) + n
T(n) = T(n-k) + (n-(k-1)) + (n-(k-2)) + ... + (n-1) + n
Assume (n-k)th is 0th task means n=k
T(n) = T(n-n) + (n-n+1) + (n-n+2) + ... + (n-1) + n
T(n) = T(0) + 1 + 2 + 3 + ... + n
T(n) = 1 + n(n+1)/2 ⋍ n²
hence Time Complexity = 𝘖(n²)
Example 3
test(int n){
if(n>0){
for(int i=0; i<n; i=i*2){
//statement
}
test(n-1);
}
}
// T(n) = T(n-1) + log₂(n) = 𝘖(nlog₂(n))
Calculation:
Base case
T(0) = 1
Time taken by nth task:-
T(n) = T(n-1) + log₂(n)
T(n-1) = T(n-2) + log₂(n-1)
T(n-2) = T(n-3) + log₂(n-2)
..
..
T(n) = T(n-3) + log₂(n-2) + log₂(n-1) + log₂(n)
T(n) = T(n-k) + log₂1 + log₂2 + ... + log₂(n-1) + log₂(n)
Assume (n-k)th is 0th task means n=k
T(n) = T(0) + log₂(n)!
T(n) = 1 + nlog₂(n) ⋍ nlog₂(n)
hence Time Complexity = 𝘖(nlog₂(n))
Example 4
test(int n){
if(n>0){
//statement
test(n-1);
test(n-1);
}
}
// T(n) = 2T(n-1) + 1 = 𝘖(2ⁿ)
Calculation:
Base case
T(0) = 1
Time taken by nth task:-
T(n) = 2T(n-1) + 1
T(n-1) = 2T(n-2) + 1
T(n-2) = 2T(n-3) + 1
..
..
T(n) = 2[2[2T(n-3) + 1] + 1] + 1
T(n) = 2³T(n-3) + 2² + 2 + 1
T(n) = 2ᵏT(n-k) + 2ᵏ⁻¹ + 2ᵏ⁻² + .. + 2² + 2 + 1
Assume (n-k)th is 0th task means n=k
T(n) = 2ⁿT(0) + (2ⁿ-1)
T(n) = 2ⁿ + (2ⁿ-1) ⋍ 2ⁿ
hence Time Complexity = 𝘖(2ⁿ)
Example 5
test(int n){
if(n>0){
//statement
test(n-1);
test(n-1);
test(n-1);
}
}
T(n) = 3T(n-1) + 1
Time Complexity = 𝘖(3ⁿ)
Example 6
test(int n){
if(n>0){
for(int i=0; i<n; i++){
//statement
}
test(n-1);
test(n-1);
}
}
//
T(n) = 2T(n-1) + n
Time Complexity = 𝘖(n2ⁿ)
Example 7
test(int n){
if(n>0){
//statement
test(n/2);
}
}
Base case
T(1) = 1
T(n) = T(n/2) + 1
T(n/2) = T(n/2²) + 1
T(n) = [T(n/2²) + 1] + 1
T(n) = T(n/2ᵏ) + k
Assume (n/2ᵏ)th is last task means
n/2ᵏ = 1
2ᵏ = n
k = log₂(n)
T(n) = T(1) + log₂(n) = 1 + log₂(n) ⋍ log₂(n)
hence Time Complexity = 𝘖(log₂(n))
Example 8
test(int n){
if(n>0){
for(int i=0; i<n; i++){
//statement
}
test(n/2);
}
}
Base case
T(1) = 1
T(n) = T(n/2) + n
T(n/2) = T(n/2²) + n/2
T(n) = [T(n/2²) + n/2] + n
T(n) = T(n/2ᵏ) + n/2ᵏ⁻¹ + n/2ᵏ⁻² + .. + n/2² + n/2 + n
Assume (n/2ᵏ)th is last task means
n/2ᵏ = 1
2ᵏ = n
k = log₂(n)
T(n) = T(1) + n[1/2ᵏ⁻¹ + 1/2ᵏ⁻² + .. + 1/2 + 1]
T(n) = 1 + n[1 + 1] = 1 + 2n ⋍ n
hence Time Complexity = 𝘖(n)
Example 9
test(int n){
if(n>0){
//statement
test(n/2);
test(n/2);
}
}
T(n) = 2T(n/2) + 1
T(n) = 2ᵏT(n/2ᵏ) + k + k-1 + k-2 + ... + 1
Assume n/2ᵏ = 1 means k = log₂(n)
T(n) = nT(1) + k(k+1)/2 ⋍ n + (log₂(n))² ⋍ n
hence Time Complexity = 𝘖(n)
Example 10
Quick Sort when pivot is middle element:-
quickSort(int[] arr, int low, int high) {
if (low < high){
int pi = partition(arr, low, high); // n
quickSort(arr, low, pi - 1); // T(n/2)
quickSort(arr, pi + 1, high); // T(n/2)
}
}
Base case
T(1) = 1
T(n) = 2T(n/2) + n
T(n/2) = 2T(n/2²) + n/2
T(n) = 2[2T(n/2²) + n/2] + n
T(n) = 2ᵏT(n/2ᵏ) + n + n + ... + n
T(n) = 2ᵏT(n/2ᵏ) + nk
Assume (n/2ᵏ)th is last task means
n/2ᵏ = 1
2ᵏ = n
k = log₂(n)
T(n) = nT(1) + nlog₂(n)
T(n) = n + nlog₂(n) = nlog₂(n)
Time Complexity = 𝘖(nlog₂(n))
Asymptotic Notations
We can represent the function complexity in following ways:-
| Symbol | Name | Bound |
|---|---|---|
| 𝘖 | big-oh | upper bound |
| Ω | big-omega | lower bound |
| ⍬ | big-theta | average bound |
Example 1
For e.g. f(n) = 2n + 3
can be represented as
𝘖(n) or any notation with higher weightage such as 𝘖(nlog₂n) or 𝘖(n²) or 𝘖(n³) ...
Ω(n) or any notation with lower weightage such as Ω(√n), Ω(log₂n), Ω(1) ...
⍬(n) and only ⍬(n) since this is average bound
Ideally you represent the function complexity to nearest type of complexity so in above case 𝘖(n), Ω(n), ⍬(n) are best representations.
Example 2
f(n) = 2n² + 3n + 4
1n² ≤ 2n² + 3n + 4 ≤ 9n²
can be represented as 𝘖(n²), Ω(n²), or ⍬(n²)
Example 3
f(n) = n²log₂n + n
n²log₂n ≤ 2n²log₂n + n ≤ 3n²log₂n
can be represented as 𝘖(n²log₂n), Ω(n²log₂n), or ⍬(n²log₂n)
Example 4
f(n) = !n = nx(n-1)x(n-2)x ...x2x1 = nⁿ
n ≤ !n ≤ nⁿ
can be represented as 𝘖(nⁿ) upper-bound, Ω(n) lower-bound
can not be represented as ⍬ since there is no common average-bound.
Example 5
f(n) = log!n = log(nx(n-1)x(n-2)x ...x2x1) = log(nⁿ) = nlog(n)
1 ≤ log!n ≤ nlog(n)
can be represented as 𝘖(nlog(n)) upper-bound, Ω(1) lower-bound
can not be represented as ⍬ since there is no common average-bound.
- It is always preferable to represent complexity in big-theta ⍬, if possible, which is more accurate and tight bound.
- Big-oh 𝘖(n) is the most popular notation to represent function complexity which you come across.
Note: Do not mix these notations with best case, worst case, or average case time complexity. All type of cases can be represented by 𝘖, Ω, and ⍬ notations.
