SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.
COMPUTATIONAL COMPLEXITY
Computation refers to solving of problems and writing proper algorithm to
solve them.
Complexity refers to parameters required to determine how much resource
required to execute the algorithm in efficient manner. These resources
includes:
1. Time complexity: time to run the algorithm
2. Space complexity: storage needed to run the algorithm
Thus complexity measures the performance of an algorithm. It is not the
absolute measure of performance and efficiency of an algorithm but it
compares different algorithms for efficiency depending on the increase of
data size. Out of two resources mentioned above time complexity is
considered to judge the performance of an algorithm.
Big O notation:
It depicts the algorithms growth rate depending on input size i.e it
determines the upper bound time it takes to execute a particular algorithm
depending on the input size. Big O notation is a function of N where N is
the size of the input to the algorithm. But while describing the growth rate
we will consider the term which can affect the performance of an
algorithm. It provides a standardized way to compare the efficiency of
different algorithms in terms of their worst-case performance.
Dominant term: The dominant term is the term that grows the fastest with
the increase of input size (N).
Page 1 of 14
SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.)
Big Oh notation is denoted as O(f(n)), where f(n) is a function that
represents the number of operations (steps) that an algorithm performs to
solve a problem of size n. The above diagram shows different type of
growth rates as per input size,
Function: f(n) = 3n3 + 2n2 + 5n + 1
1. Dominant Term: 3n3
2. Order of Growth: Cubic (n3)
3. Big O Notation: O(n3)
4. Simplified Notation: O(n3)
Performance of an algorithm can be judged in three ways
Best case complexity (minimum time taken for input size n)
Worst case complexity (maximum time taken for input size n)
Average case complexity: (average time taken for input size n)
Calculating complexity:
Rules:
1. Break the codes into fragments (containing sequential statements,
conditional statements, iterative statements)
2. For each fragment generate maximum possible time to execute and
join each of the fragments by addition.
3. For loops/nested loop use multiplicative rule to find max time to
execute the loop statements for each iteration.
4. Remove the non-dominant term from final function.
5. Remove constants from the function.
6. Consider the dominant term as the final BigO notation value.
Page 2 of 14
SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.)
Check the code below:
int x=2; Fragment 1
x=x+4;
for(int i=0;i<n;i++)
{
Fragment 2
int a=i+1;
a++;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++) Fragment 3
int k=i+j;
}
if(x>a) Fragment 4
x=x+a;
else
{
for(int i=0;i<n;i++)
{ Fragment 5
if(i%2==0)
x=x+i;
}
}
Fragment 1: As sequential statement takes constant time to execute, so let
us assume that fragment 1 statements will be executed at constant time c1.
Page 3 of 14
SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.)
Fragment 2: For loop based sequential statements , let us assume that it
takes constant time c2 to execute. Now loop iterates for n times. So n times
loop statements are executed, so final time will be c2*n.
Fragment 3: For nested loop based sequential statements , let us assume
that it takes constant time c3 to execute for inner loop. Now outer loop
iterates for n times and inner loop iterates for n times for each iteration of
outer loop.
So when i=0, inner loop iterates sequential statements for n times at
constant time c3. So time taken c3*n.
So for i=0 to n, total time=c3*n+c3.n+c3.n+ …… n times
=c3*n*(1+1+…… n times)
=c3*n*1*n=c3*n2
Fragment 4: Let us assume conditional statement executed for constant
time c4 and sequential statements executed at constant time c5.
So total time=c4+c5
Fragment 5: Here conditional statement executed for constant time c6 and
sequential statements executed at constant time c7. Both the statements are
executed for n times. So total time=(c6+c7)*n;
So total time= c1+ c2*n + c3*n2 + c4+c5 + (c6+c7)*n
=c3*n2 [removing non-dominant term, considering dominant
term which can affect performance of algorithm]
=O(n2) [removing constants]
Linear Search (time complexity)
Best case : O(1)
Average case : O(n)
Worst case: O(n)
Page 4 of 14
SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.)
Binary search (time complexity)
Best case : O(1)
Average case : O(log2n)
Worst case: O(log2n)
Derivation: (worst case)
Say T(n): time taken to search the element from n elements in sorted array.
So, for first iteration of binary search let us assume constant time c
required to find mid element of the array and checking for condition. So if
the searched element is not found in first iteration the array is divided in
two halves and any one half is considered for iteration. So
T(n)=c + T(n/2) …… (1)
T(n/2)= c+ T(n/4) ….. (2)
Substitute (2) in (1)
T(n)=T(n/4)+ 2c …… (3)
T(n/4)=c+ T(n/8) ……(4)
Substitute (4) in (3)
T(n)=T(n/8)+3c…… (5)
So for iteration 1…….. size of array =n/2
So for iteration 2…….. size of array =n/4
So for iteration 3…….. size of array =n/8
…..
So for iteration k…….. size of array =1
So at kth iteration:
T(n)=T(n/2k) + kc …..(6)
We have seen that in binary search finally array is considered with 1
element to be searched which takes constant time as T(1).
Page 5 of 14
SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.)
So, T(n/2k)=T(1)
n/2k = 1
n=2k
log2n = log2 2k
k=log2n
Substitute in (6)
T(n)= T(n/n) + c.log2n [ as n=2k]
=T(1) + clogn
T(n)=O(logn)
Bubble sort(time complexity)
Best case : O(n) , swap: O(1)
Average case : O(n2) , swap: O(n2)
Worst case: O(n2) , swap: O(n2)
Modified logic of bubble sort:
void bubble(int a[])
{
int c=0; //only used to get an idea about complexity
for(int i=0;i<[Link];i++)
{
int f=0;
for(int j=0;j<[Link]-i-1;j++)
{
c++;
if(a[j]>a[j+1])
{
Page 6 of 14
SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.)
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
f=1;
}
}
if(f==0)
break;
}
[Link]("number of comparison="+c);
}
In bubble sort having n elements, for first iteration it will be n-1
comparison.
for second iteration it will be n-2 comparison.
…….
for n-1 iteration it will be 1 comparison.
So T(n)=(n-1) + (n-2) + (n-3) + …… +1
= (n-1)[2(n-1)+ (n-1-1)*(-1)]/2 =(n-1)[2n-2-n+2]/2=(n-1)n/2
T(n)= n2/2 + n/2 = O(n2)
Best case:
Say for the array:
1234
Iteration 1: 3 comparison
Loop ends as array already sorted
So T(n)=n-1= O(n)
Page 7 of 14
SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.)
Selection sort(time complexity)
Best case : O(n2) , swap: O(1)
Average case : O(n2), swap: O(n)
Worst case: O(n2), swap: O(n)
WORST CASE:
8 7 6 5
For iteration 1: 3 comparisons
For iteration 2: 2 comparisons
For iteration 3: 1 comparison
Best case:
5678
For iteration 1: 3 comparison
For iteration 2: 2 comparison
For iteration 3: 1 comparison
In both cases: T(n)=1+2+3+……+(n-1)=n(n-1)/2=O(n2).
Insertion sort:
Best case : O(n) , swap: O(1)
Average case : O(n2), swap: O(n2)
Worst case: O(n2), swap: O(n2)
Page 8 of 14
SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.)
Best case:
1234
For iteration 1: comparison 1
For iteration 2: comparison 1
For iteration 3: comparison 1
T(n)=1+1+ …. +(n-1)= O(n)
Worst case:
4321
For iteration 1: comparison 1
For iteration 2: comparison 2
For iteration 3: comparison 3
T(n)=1+2+3+….+ (n-1)= n(n-1)/2=O(n2)
Average case:
25431
For iteration 1: comparison 1,swap=0
For iteration 2: comparison 2,swap=1
For iteration 3: comparison 3,swap=2
For iteration 4: comparison 4,swap=3
T(5)=9
Swaps=6
**************************************************************
Page 9 of 14
SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.)
Updated sorting codes:
//Here c and swap are extra variables used for testing purpose. You have to
//discard them while using them in your code.
class Sort
{
static void bubble(int a[])
{
int c=0,swap=0;//variables used for testing purpose only
for(int i=0;i<[Link];i++)
{
int f=0;
for(int j=0;j<[Link]-i-1;j++)
{
c++;
if(a[j]>a[j+1])
{
swap++;
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
f=1;
}
}
if(f==0)
break;
}
[Link]("number of comparison="+c);
Page 10 of 14
SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.)
[Link]("number of swaps="+swap);
disp(a);
}
static void selection(int a[])
{
int c=0,swap=0; //variables used for testing purpose only
for(int i=0;i<[Link];i++)
{
int min=i;
for(int j=i+1;j<[Link];j++)
{
c++;
if(a[j]<a[min])
min=j;
}
if(i!=min)
{
swap++;
int t=a[i];
a[i]=a[min];
a[min]=t;
}
}
[Link]("number of comparison="+c);
[Link]("number of swaps="+swap);
disp(a);
Page 11 of 14
SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.)
static void insertion(int a[])
{
int c=0,swap=0;//variables used for testing purpose only
for(int i=1;i<[Link];i++)
{
int j=i-1;
int key=a[i];
while(j>=0)
{
c++;
if(a[j]>key)
{
swap++;
a[j+1]=a[j];
j--;
}
else
break;
a[j+1]=key;
Page 12 of 14
SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.)
[Link]("number of comparison="+c);
[Link]("number of swaps="+swap);
disp(a);
}
static void disp(int a[])
{
[Link]("After sort");
for(int i=0;i<[Link];i++)
[Link](a[i]+" ");
[Link]();
}
Some ISC based questions solved.
1. Define computational complexity.
2. Define Big Oh notation.
3. Compare O(logn) with O(2n). Which one is better and why?
Ans: 1) In computer science, the computational complexity or
simply complexity of an algorithm is the amount of resources (time and space)
required to run it. The complexity measures the performance of an algorithm.
It is not the absolute measure of performance and efficiency of an algorithm
but it compares different algorithms for efficiency depending on the increase
of data size.
Page 13 of 14
SALT LAKE SCHOOL SUBHANKAR BOSE (Computer Sc. Dept.)
2) Big Oh notation: Big O notation is a mathematical notation used to describe
the worst-case time/space complexity or efficiency of an algorithm. It provides a
way to compare the performance of different algorithms, data structures, and
predicts how they will behave as the input size increases. It provides an upper
limit on the time taken by an algorithm in terms of the size of the input. It’s
denoted as O(f(n)), where f(n) is a function that represents the number of
operations (steps) that an algorithm performs to solve a problem of size n.
Example : Worst case time complexity of Bubble Sort algorithm: O(n2).
3) Here let us compare the time complexity of both the big o notation in terms of
different value of input size n
log2n= (log10n)/(log102)
n O(log2n) O(2n)
1 0 [ log101/log102] 2
2 1 [ log102/log102] 4
3 ≈1.584 [ log103/log102] 8
4 2 [ log104/log102] 16
From the table we can see that as the input size increases time taken by O(logn)
is much lesser than time taken by O(2n). So algorithm with complexity O(logn)
is better than algorithm with complexity O(2n).
O(logn) is time complexity of Binary search algorithm while O(2 n) is the time
complexity for algorithm of deriving nth term of Fibonacci series using recursion
logic.
********************************************************
Page 14 of 14