UNIT - I

Introduction: Algorithm, Performance Analysis-Space complexity, Time complexity,

Asymptotic Notations- Big oh notation, Omega notation, Theta notation and little oh
notation. Divide and conquer: General method, applications-Binary search, Quick sort,
Merge sort, Strassen’s matrix multiplication.(VAAGESWARI COLLEGE OF ENGG-CSE)

Algorithm:
It is a combination of a sequence of finite steps to solve a problem.
Properties:
Input: An algorithm can have zero or more inputs.
Output: An algorithm should produce at least one output
Definiteness: Each instruction must be clear and unambiguous.
Finiteness: An algorithm should consist of a finite number of steps and terminate after a
finite set of instructions.
Effectiveness: An algorithm should be effective, which implies that it should be traceable
manually.
Steps needed to design an Algorithm:
1. Problem definition

2. Select design technology

3. Draw flowchart

4. Testing

5. Implementation

6. Ananysis

We can describe an algorithm in many ways:

1. Step-form: This is a straightforward textual representation where each step of the
algorithm is described in sequential order.
2. Flowchart: A flowchart is a graphical representation of an algorithm.
3. Pseudocode: Pseudocode is a step-by-step description of an algorithm in a code-like
structure using plain English text.
Algorithm Example
Aim: Find the sum of any two values
Sol:
Step1: Start
Step2: Read a,b
Step3: Calculate sum=a+b
Step4: Print sum
Step5: Stop
Performance Analysis
The efficiency of an Algorithm can be decided by measuring the performance of an
algorithm. We can measure the performance of an algorithm by computing amount of time
and storage.

Space complexity:

The amount of space required to store an algorithm in memory is called space complexity.

To compute the space complexity we use two factors:

Constant (fixed part) and instance characteristics (variable part)

S(p)=C+Sp
Where C is a constant ie. fixed part and it denotes the space of inputs and outputs. This
space is an amount of space taken by instruction, variables and identifiers.
Sp is a space dependent upon instance characteristics. This is a variable part whose space
requirement depends on particular problem instance. Consider various examples of
algorithms to compute the space complexity.
Example 1:
Algorithm Add (a,b,c)
{

// a,b, and c are of floating type.

return a+b+c;

Example 2:

Algorithm Add (x,n)

// sum and x(i] are floating type.

sum:=0.0;

for i:=l to n do

sum:=sum+x[i]:

return sum;

Example 3:
Algorithm Add (x,n)
{
//x[i] is of floating type
return (Add (x,n-l)+x(n]);
}
The space requirement for algorithm given in example 1 is
S(p)=C(Sp=0)
If we assume a,b and c occupy one word size then total size comes to be 3.

The space requirement for algorithm given in example 2 is

S(p) >= (n +3)
The 'n' space required for x[ |, one space for n, one for i and one for sum.

The space requirement for the algorithm given in example 3 is

S(p) >= 3(n+1)
The internal stack used for recursion includes space for formal parameters, local variables
and return address. The space required by each call to function Add requires at least three
words (space for n values + space for return address + pointer to x []).
The depth of recursion in n+1 (n times call to function and one return call). The
recursion stack space will be >= 3(n+1).

Time complexity:

The amount of time required to run an algorithm is called time complexity

T(P)=Time complexity of an algorithm P

T(P)=Compilation time(P)+Runtime(P)

Compiler + Processor

s/w + h/w

Language of compiler + Type of processor

Best Case, Worst Case and Average Case Analysis

If an algorithm takes the minimum amount of time for its execution, then it is called the
best-case time complexity.

For example: While searching a particular element by using sequential search we get the
desired element at first place itself then it is called best case time complexity.

If an algorithm takes the maximum amount of time for its execution, then it is called the
worst-case time complexity.

For example: While searching an element by using linear searching method if desired
element is placed at the end of the list then we get worst time complexity.
If an algorithm takes an average amount of time for its execution, then it is called the
Average-case time complexity.

For calculating the time complexity, only run time is considered. It is difficult to compute the
time complexity in terms of physically clocked time. Because runtime depends on many
factors such as system load, number of other programs running and processor speed.
For avoiding this, we are using frequency count is basically a count denoting number of
times of execution of statement.

The method to determine the step count of an algorithm is to build a table in which we list
the total number of steps contributes by each statement.
First determine the number of steps per execution (s/e) of the statement and the total
number of times (ie., frequency) each statement is executed. By combining these two
quantities, the total contribution of all statements, the step count for the entire algorithm is
obtained.

We can analyze the time complexity of an algorithm in two ways:

Posteriori Analysis: This method depends on the language of the compiler and the type of
processor.

A Priori Analysis: This method is independent of the language compiler and the type of
hardware.
A priori Analysis:
It is a determination of order of magnitude of statements.

Ex1:
main()
{
c=a+b;----1
}-------- O(1)

Ex:2
main()
{
x=y+z;------------- 1
for(i=1;i<=n;i++)---n
x=y+z;
a=b+c;--------------1
} ----------
1+n+1 =n+2 =O(n)

Ex 3:
main()
{
x=y+z;---------------1
for(i=1;i<=n;i++)----n
x=z+1;
for(i=1;i<n;i++)-------n
*
for(j=1;j<n;j++)-------n
x=y+z;
} -----------------
n²+n+1 =O(n²)

Ex 4:
main()
{
i=1;
while(i<=n)
{
x=y+z;
a=b+c;
i=2*i;
}
} -------O(logn)
Ex 5:
main()
{
i=1;
while(n>1)
{
n=n/2;
x=y+z;
a=b+c;
}
} -------O(logn)

Ex 6:
main()
{
i=2;
while(i<=n)
{
i=i²;
x=y+z;
a=b+c;
}
}
-------O(log(logn))

Ex 7:
main()
{
while(n>2)
{
n=√n;
x=y;
a=b;
}
}
-------O(log(logn))
Asymptotic Notations

To choose the best algorithm, we need to check efficiency of each algorithm.

The efficiency can be measured by computing time complexity of each algorithm. Asymptotic
notation is a shorthand way to represent the time complexity.

Using asymptotic notation we can give time complexity as "fastest possible", “slowest
possible” or "average time".

Various notations such as Ω, Θ and O and are called asymptotic notions.

They are 3 asymptotic notations are mostly used to represent time complexity of algorithm.

1.Big oh (O)notation

2.Big omega (Ω) notation

3.Theta(Θ) notation

4.Little oh notation

5.Little omega(Ω) notation

1.Big oh (O)notation

This notation mainly represents the upper bound of an algorithm's runtime.

Big oh (O)notation is useful for calculating the maximum amount of execution time.

Using Big-O notation, we can determine the worst-case time complexity.

Def: Let f(n) and g(n) are two non-negative functions. The function f(n)=O(g(n)) iff there exist
positive constants c and n0 such that f(n)<=c*g(n) for all n, n>=n0

Formulae:
f(n)<=c g(n) n>= n0, c>0, n0>=1

Ex:
f(n)=3n+2 and g(n)=n

here c=3 here c=4

f(n)<=c*g(n) f(n)<=c*g(n)
3n+2<=3n 3n+2<=4n
5<=3---F (n=1) 5<=4---F (n=1)
8<=6---F (n=2) 8<=8---T (n=2)
11<=9---F (n=3) 11<=12---T (n=3)

Therefore 3n+2<=4n for all n>=2

The following graph the curve for Big Oh Notation.

2.Big omega (Ω) notation

It represents the lower bound of an algorithm’s runtime.

Big Omega (Ω) notation is used to calculate the minimum amount of time.

This notation describes the best-case time complexity.

Def: Let f(n) and g(n) are two non-negative functions. The function f(n)= Ω(g(n)) iff there exist
positive constants c and n0 such that f(n)>=c*g(n) for all n, n>=n0

Formulae: f(n)>=c g(n) n>= n0, c>0, n0>=1

where c is constant, n is function
Example: f(n)=3n +2

Formulae: f(n)>=c g(n) n>=n0, c>0, n0>=1

Given Functions:

f(n)=2n +3

g(n)= n

First, let's test with c=3:

3n+2>=3n

5>=3---True (n=1)

8>=6---True (n=2)

Therefore 3n+2>=3n for all n>=2

The following graph the curve for Big Omega Notation.

f(n)= Ω(g(n))

3.  -Theta notation
It represents the average bound of an algorithm’s running time.
Theta (Θ) notation is used to calculate the average amount of time.
This notation describes the average-case time complexity of an algorithm.

Definition: Let f(n) and g(n) be two non-negative functions. f(n) is said to be θ(g(n)) if and
only if there exists positive constants ‘c1’, ‘c2’ and ‘n0’ such that c1 * g(n) ≤ f(n) ≤ c2 * g(n) for
all non-negative values of n. where n ≥ n0.

Formulae: c1g(n)<=f(n)<=c2 g(n) n>= n0, c>0, n0>=1

Example: f(n)=3n+2
Formulae: c1 g(n)<=f(n)<=c2g(n)

f(n)=2n+3
3n+2>=3n for all n>=2
3n+2<=4n for all n>=2

Note: n should be equal in both cases

Therefore 3n<=3n+2<=4n for all n>=2

The following graph the curve for Theta Notation.

4.Little oh notation(o)
Little-o notation is used to describe an upper bound that cannot be tight. In other words, it
represents a loose upper bound of f(n).

The function f(n)=O(g(n)) if and only if

Example on little o asymptotic notation:

1.If f(n) = n2 and g(n) = n3 then check whether
f(n) = o(g(n)) or not.

The result is 0, and it satisfies the equation mentioned above. So, we can say that f(n) =
o(g(n)).

5.Little omega(ω) notation

Another asymptotic notation is Little-Omega notation, denoted by ω. Little-Omega (ω)
notation is used to describe a loose lower bound of f(n).

The function f(n)= ω(g(n)) if and only if

DIVIDE AND CONQUER

In this strategy, the big problem is broken into smaller sub problems, and solutions to these
sub problems are obtained.

Divide: Divide the given big problem into a few sub problems.

Conquer: Conquer the sub problems by calling recursively so that we will get the solution to
each sub problem.

Combine: Combine the solutions to the sub problems so that we will obtain the final
solution to the problem.

GENERAL METHOD

Algorithm D And C(P)

if small(P) then return S(P);

else

divide P into smaller instances

P1, P2… Pk, k>=1;

Apply D And C to each of these sub problems;

return combine (D And C(P1), D And C(P2),…….,D And C(Pk));

Applications of Divide and Conquer Algorithm

The applications of the Divide and Conquer algorithm are as follows:

• Binary Search

• Merge Sort

• Quick Sort

• Strassen’s Matrix Multiplication

Advantages of Divide and Conquer Algorithm
It efficiently uses cache memory without occupying much space because it solves simple
subproblems within the cache memory instead of accessing the slower main memory.

It’s more effective than the Brute Force approach.

These techniques work well with parallel processing systems without needing any
adjustments.

Disadvantages of Divide and Conquer

Recursion is incorporated into the majority of its algorithms; hence it requires intensive
memory management.

The space could be overused by an explicit stack.

If the recursion is carried through rigorously beyond the CPU stack, the system can even
crash.

Binary search

Searching is the process of finding the position of a specific value in a list of values.

Binary search follows the divide and conquer approach in which the list is divided into two
halves, and the item is compared with the middle element of the list.

If the match is found then, the location of the middle element is returned.

Otherwise, we search into either of the halves depending upon the result produced through
the match.

We have the sorted array: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20].
We start with low = 0 and high = 9 (inclusive), representing the entire array.
Calculate the middle index: mid = (low + high) / 2 = (0 + 9) / 2 = 4.
 Check value at index 4: array[4] = 10.
Compare 10 with the target 12.
 Since 12 is greater than 10, the target must be on the right side.
Set low = mid + 1 = 4 + 1 = 5.
 We're now searching within the subarray [12, 14, 16, 18, 20].
Calculate the new middle index: mid = (low + high) / 2 = (5 + 9) / 2 = 7.
 Check value at index 7: array[7] = 16.
Compare 16 with the target 12.
 Since 12 is less than 16, the target must be on the left side.
Set high = mid - 1 = 7 - 1 = 6.
 We're now searching within the subarray [12, 14].
Calculate the new middle index: mid = (low + high) / 2 = (5 + 6) / 2 = 5.
 Check value at index 5: array[5] = 12.
We found the target 12 at index 5. Search complete.
Recurrence Relation

1.Initial Problem Size: Suppose we have a sorted array of size n.

2.Divide and Conquer: At each step, binary search divides the problem size approximately in
half. So, if the current problem size is n, the next problem size will be n/2.

3.Recurrence Relation: The time complexity

T(n)=2T(n/2)+O(1)

Here:

T(n/2)represents the time required to search in the reduced size of the array.

O(1) represents the constant time required to perform the comparison at each step (checking
the middle element).
Time Complexity

Best Case: O(1) The best-case scenario occurs when the middle element is the target element
in the very first comparison. In this case, the search is completed in constant time.

Average Case: O(logn) On average, binary search will require about logn comparisons, where
n is the number of elements in the list. This is because each comparison effectively halves
the number of elements to be searched.

Worst Case: O(logn) In the worst case, binary search still takes O(logn) time. Even though
it’s the maximum number of steps needed, it grows logarithmically with the number of
elements, making it very efficient compared to linear search.
Advantages of Binary Search Algorithm

1. When it comes to comparing large data, it is quite efficient as it works on the

technique to eliminate half of the array element.

2. It has less compilation time and thus better time complexity.

3. As it breaks the array in half, it is considered an improvement over linear search.

Disadvantages of Binary Search Algorithm

1. It can only be implemented over a sorted array.

2. The process of sorting and searching in an unsorted array will take time. Thus, binary
search is not a good option in such cases.

MERGE SORT

The merge sort is sorting algorithm that uses the divide and conquers strategy. In this
method division is dynamically carried out.
Merge sort on an input array with n elements consists of three steps:
Divide: partition array into two sub lists s1 and s2 with n/2 elements each.
Conquer: recursively sort s1 and s2.
Combine: merge s1 and s2 into a unique sorted group.

Algorithm
Algorithm MERGESORT (a,low, high)
{
if (low < high)
{
mid := (low +high)/2
MERGESORT(a,low, mid);
MERGESORT(a,mid+1, high);
MERGE(a,low,mid,high); // combine the results
}
}
Algorithm merge(a,low,mid,high)
{
i=low;
j=mid+1;
k=low;
while(i<=mid && j<=high)
{
if(a[i]<=a[j])
{
b[k]=a[i];
i++;
k++;
}
else
{
b[k]=a[j];
j++;
k++;
}
k++;
}
if(i>mid)
{
while(j<=high)
{
b[k]=a[j];
j++;
k++;
}
else
while(i<=mid)
{
b[k]=a[i];
i++;
k++;
}
}
}
Example:

Initially, we pass the array A along with left = 1, and right = 10 as inputs to the an algorithm
Merge_Sort(). The input array A is then split into two equal-sized sub-arrays using the
formula: middle = (1 + 10) / 2 = 5.

The sub-arrays [75,.., 20] and [40,.., 30] are then passed onto the recursive procedural calls
Merge_Sort(A, 1, 5) and Merge_Sort(A, 6, 10), respectively, which again divides each of these
arrays into smaller sub-arrays. The recursive function terminates when it encounters a sub-
array of size 1 (base condition).

That is, no further division is possible from that sub-array. For example, steps 5 and 6
indicate the generation of two sub-arrays of size 1, that is, [75] and [20].

The algorithm then combines these two sub-arrays and produces a sorted array [10, 75]
using an algoritm Merge(). We then backtrack and combine the sub-array [7] with this array
[10, 75] to generate a new sorted array [7, 10, 75].

These processes of recursive calling and merging are repeated until we generate the final
sorted array [6, 7, 10, 20, 30, 30, 40, 50, 75, 99].

The merge sort is the only stable sorting algorithm, whereas quicksort is not a stable sorting
method. A sorting method is said to be stable if, at the end of the process, identical elements
occur in the same order as that of the original list
Time Complexity of Merge Sort Algorithm

Case Time Complexity of Merge Sort

Best Case O(n*logn)

Average Case O(n*logn)

Worst Case O(n*logn)

Advantages of Merge Sort:

Stable Sort
Efficient Time Complexity
Works Well with Large Data
Divides and Conquers
Can Handle Linked Lists

Disadvantages of Merge Sort:

Extra Space Requirement
Slower for Small Datasets
Not an In-place Sort
Recursive Overhead

Quick Sort
Quick Sort is a highly efficient, comparison-based sorting algorithm that follows the divide-
and-conquer paradigm. It works by selecting a pivot element from the array, partitioning the
remaining elements into two sub-arrays — one with elements less than the pivot and
another with elements greater than the pivot. The algorithm then recursively applies the
same process to each sub-array until the entire array is sorted.

Example
Let us consider the input array, A [75, 10, 7, 6, 20, 40, 50, 30, 99, 30].
Here, p = 1, r = 10. Then, Quick_Sort(A[75, 10, …, 30], 1, 10). Since 1 < 10, q = Partition(A,
1, 10), pivot = A[r] = 30, i = p - 1 = 0.

Iteration-1 (j = 1, i = 0):
A[1] = 75 is not less than the pivot 30.
[75, 10, 7, 6, 20, 40, 50, 30, 99, 30]

Iteration-2 (j = 2, i = 0):
A[2] = 10 <= 30.
i = i + 1 = 1. Swap A[1] with A[2].
[10, 75, 7, 6, 20, 40, 50, 30, 99, 30]

Iteration-3 (j = 3, i = 1):
A[3] = 7 <= 30.
i = i + 1 = 2. Swap A[2] with A[3].
[10, 7, 75, 6, 20, 40, 50, 30, 99, 30]

Iteration-4 (j = 4, i = 2):
A[4] = 6 <= 30.
i = i + 1 = 3. Swap A[3] with A[4].
[10, 7, 6, 75, 20, 40, 50, 30, 99, 30]

Iteration-5 (j = 5, i = 3):
A[5] = 20 <= 30.
i = i + 1 = 4. Swap A[4] with A[5].
[10, 7, 6, 20, 75, 40, 50, 30, 99, 30]

Iteration-6 (j = 6, i = 4):
A[6] = 40 is not less than 30.
[10, 7, 6, 20, 75, 40, 50, 30, 99, 30]

Iteration-7 (j = 7, i = 4):
A[7] = 50 is not less than 30.
[10, 7, 6, 20, 75, 40, 50, 30, 99, 30]

Iteration-8 (j = 8, i = 4):
A[8] = 30 <= 30.
i = i + 1 = 5. Swap A[5] with A[8].
[10, 7, 6, 20, 30, 40, 50, 75, 99, 30]

Iteration-9 (j = 9, i = 5):
A[9] = 99 is not less than 30.
[10, 7, 6, 20, 30, 40, 50, 75, 99, 30]

After Iteration-9 (i = 5):

i = i + 1 = 6. Swap A[6] with A[10].
[10, 7, 6, 20, 30, 30, 50, 75, 99, 40]. Return value = 6. Then, q = 6.

This will lead to the following splits:

Quick_Sort(A[10, 7, …, 40], 1, 5)
Quick_Sort(A[10, 7, …, 40], 7, 10)

Now, let us consider the first split Quick_Sort(A[10, 7, …, 40], 1, 5). Here, p = 1, r = 5, pivot
= A[5] = 30. It may be noted that A[j] <= pivot, for all values of j (1 to 4), since this sub
array has already been in a sorted order. Hence, the return value i = 0 from Partition(A[10,
7, …, 40], 1, 5). Thus, there will be no more recursive calls from the first split.
Let us consider the second split Quick_Sort(A[10, 7, …, 40], 7, 10). Here, p = 7, r = 10, pivot
= A[10] = 40. After the execution of Partition(A[10, 7, …, 40], 7, 10), the resulting array:
[10, 7, 6, 20, 30, 30, 40, 75, 99, 50] with the return value 8. In the next invocation of
Quick_Sort(A[10, 7, …, 50], 9, 10), the pivot 50 gets swapped with 75 and results in [10, 7,
6, 20, 30, 30, 40, 50, 99, 75]. It takes one more invocation of Quick_Sort() to get the final
sorted array: [6, 7, 10, 20, 30, 30, 40, 50, 75, 99].

Algorithm:
Algorithm QuickSort(a,i,j)
{
If(i<j)
{
Loc=partition(a,i,j)
QuickSort(a,i,loc-1);
QuickSort(a,loc+1,i);
}
}

Algorithm partition(a,i,j)
{
pivot=a[i];
i=0;
j=n-1;
while(i<j)
{
while(a[i]<=pivot)
{
i++;
}
while(a[j]>pivot)
{
j--;
}
if(i<j)
{
swap(a[i],a[j]);
}
}
swap(a[pivot],a[j])
return j;
}
Advantages of Quick Sort:
 It is a divide-and-conquer algorithm that makes it easier to solve problems.
 It is efficient on large data sets.
 It has a low overhead, as it only requires a small amount of memory to function.
 It is Cache Friendly as we work on the same array to sort and do not copy data to
any auxiliary array.
 Fastest general-purpose algorithm for large data when stability is not required.

Disadvantages of Quick Sort:
 It has a worst-case time complexity of O(N^2 ), which occurs when the pivot is
chosen poorly.
 It is not a good choice for small data sets.
 It is not a stable sort, meaning that if two elements have the same key, their
relative order will not be preserved in the sorted output in case of quick sort,
because here we are swapping elements according to the pivot’s position (without
considering their original positions).
Strassen’s Matrix Multiplication