Talent Battle LiveTraining
TCSSpecific TechnicalTraining
Complexity of Algorithms
• Evaluation of Algorithms can be done based on their performance
• Performance Evaluation might require thinking about
• How much space(memory) required by the givenprogram
• How much time it will take in order to complete task
• Calculating performance on these measures called
• Space Complexity
• Time Complexity
SpaceComplexity
• The amount of memory an algorithm needs to completeits
execution.
• Total space = sum of two types of spacecomponents
• Fixed space (fixed part)
• Instruction
• Variables or constants
• Variable Space (variable part)
• Space required due to recursion(stack)
SpaceComplexity
• ToAnalyze space complexity we should focus on variable space
SpaceComplexity
Example: Algorithm Array Sum
Space Requirements for Given Algorithm
arraySum(a[],n) 1. n = 1 unit
{ 2. s = 1 unit
s =0; 3. i = 1 unit
for i=0 to n 4. a[n] = n units
{
s = s+ a[i]; 5. Total size = n +1 + 1+ 1
} = n+ 3
}
SpaceComplexity
one function Call require (space)
Example: Algorithm Array Sum(recursion)
1. return address = 1 unit
arraySum(a[],n) 2. Pointer to a = 1 unit
{ 3. Local variable n = 1 unit
if(n<=0) return 0; 4. Total size = 3 units
else
return arraysum(a[],n-1)+a[n];
} 5. Calling of function recursion(n+1)
Space requirement = 3 (n+1)
Time Complexity of Algorithm
• Amount of time required taken by algorithm to complete its
execution.
• 3 different cases
• Best case
• Average case
• Worst case
• Ω Best case
• ΘAveragecase
• O worst case
Time Complexity
•Algorithm evaluation in done on worst casecomplexity
•All algorithm complexities denoted byO
Example O(1)
O(n)
O(n2)
O(nlogn)
Time complexity Calculations
• Ignore constants (coeificients)
• Some terms dominate others
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)
• Ignore lower order terms
Constant Time
• X= 5 + (20 * 40) calculation in independent of input size(N)
X= 10 + 20*30
Y= 15 – 10
Print x+y
Total Time = O(1) + O(1) + O(1)
= 3 * O(1)
Linear Time
For x in range (0,n)
{
Print x
}
O(1) * n= O(n)
Linear Time
Y= 15 + (3 *5)
For x in range (0,n)
{
Print x
}
Total Time = O(1) + O(n) = O(n)
Quadratic Time
Y= 15 + (3 *5)
for x in range(0,n)
for y in range(0,n)
print x*y
Total Time = O(n * n ) = O(n2)
O(?)
X= 5 + (15 *20)
for(x in range(0,n)):
print x;
for (x in range(0,n))
for( y in range(0,n):
print x*y
Answer:
• Total Time = O(1) + O(n) + O(n2) = O(n2)
Logarithmic Complexity
𝒙= 𝒃𝒚 𝒕𝒉𝒆𝒏𝒚= log𝑏 𝒙
for(int j = 1;j<n; j *=c)
{
OR
for(int j = 1 ;j<n ; j / = c)
{
}
Sorting
• Arranging objects / elements in a list in specific order
• Ascending or Descending
• Types of Sorting
• Bubble sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
Bubble sort
• Simplest sorting algorithm
• Idea of comparing two adjacent elements repeatedly and swaptheir
positions if required
• i.e. repeatedly compare and swap two adjacent elements if they
exists in wrong order
• largest element is moved like a bubble at the top of the array
Example
Bubble Sort Algorithm
void bubble_sort( int A[ ], int n )
{
int temp;
for(int i = 0; i< n-1; i++){
/ / (n-i-1) is for ignoring comparisons of elements which have already been
compared in earlier iterations
for(int j = 0; j < n-i-1; j++){
if(A[ j ] > A[ j+1] ) {
/ / here swapping of positions is being done.
temp = A[ j ];
A[ j ] = A[ j+1 ];
A[ j + 1] =temp;
}
}
}
}
Selection Sort
• Sorts and array repeatedly finding the minimum element from
unsorted array and putting it atbeginning.
• Hence algorithm maintains two sub arrays
1. One sub array which is already sorted
2. Other sub array which remains unsorted
Example
a r r [ ] = 64 25 12 22 11
/ / Find the minimum element i n a r r [ 0 . . . 4 ]
/ / and place i t a t beginning
11 25 12 22 64
/ / Find the minimum element i n a r r [ 1 . . . 4 ]
/ / and place i t a t beginning o f a r r [ 1 . . . 4 ]
11 12 25 22 64
/ / Find the minimum element i n a r r [ 2 . . . 4 ]
/ / and place i t a t beginning o f a r r [ 2 . . . 4 ]
11 12 22 25 64
/ / Find the minimum element i n a r r [ 3 . . . 4 ]
/ / and place i t a t beginning o f a r r [ 3 . . . 4 ]
11 12 22 25 64
Algorithm
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(arr[j]<arr[i])
{
int temp =arr[i];
arr[i] =arr[j];
arr[j] =temp;
}
}
Insertion Sort
• Simple sorting algorithm building sorted array by choosing
one element at atime
• Works in a way we sort playing cards in our hands
Insertion Sort
Insertion Sort
Algorithm
for(i=1;i<n;i++)
{
key = arr[i];
j =i-1;
while(j>=0 && arr[j]>key)
{
arr[j+1] =arr[j];
j =j-1;
}
arr[j+1] =key;
}
