UNIT I

INTRODUCTION

Introduction : What is an Algorithm? Fundamentals of Algorithmic problem solving, Fundamentals of

the Analysis of Algorithm Efficiency, Analysis Framework, Measuring the input size, Units for
measuring Running time, Orders of Growth, Worst-case, Best- case and Average- case efficiencies

1.1 Algorithm

An algorithm is a well-defined sequential computational technique that accepts a value or a

collection of values as input and produces the output(s) needed to solve a problem.
Or we can say that an algorithm is said to be accurate if and only if it stops with the proper
output for each input instance.

Need Of The Algorithms

Algorithms are used to solve problems or automate tasks in a systematic and efficient manner.
They are a set of instructions or rules that guide the computer or software in performing a particular
task or solving a problem.
 Efficiency: Algorithms can perform tasks quickly and accurately, making them an essential
tool for tasks that require a lot of calculations or data processing.
 Consistency: Algorithms are repeatable and produce consistent results every time they are
executed. This is important when dealing with large amounts of data or complex processes.
 Scalability: Algorithms can be scaled up to handle large datasets or complex problems,
which makes them useful for applications that require processing large volumes of data.
 Automation: Algorithms can automate repetitive tasks, reducing the need for human
intervention and freeing up time for other tasks.
 Standardization: Algorithms can be standardized and shared among different teams or
organizations, making it easier for people to collaborate and share knowledge.

Overall, algorithms are an essential tool for solving problems in a variety of fields, including
computer science, engineering, data analysis, finance, and many others.

1.2 Fundamentals of Algorithmic problem solving

Algorithm Analysis
Algorithm analysis is an important part of computational complexity theory, which provides
theoretical estimation for the required resources of an algorithm to solve a specific computational
problem. Analysis of algorithms is the determination of the amount of time and space resources required
to execute it.
Important of Algorithm Analysis
 To predict the behaviour of an algorithm without implementing it on a specific computer.
 It is much more convenient to have simple measures for the efficiency of an algorithm than
to implement the algorithm and test the efficiency every time a certain parameter in the
underlying computer system changes.
1
  It is impossible to predict the exact behaviour of an algorithm. There are too many
influencing factors.
 The analysis is thus only an approximation; it is not perfect.
 More importantly, by analysing different algorithms, we can compare them to determine
the best one for our purpose.

Creating an Algorithm

Since the algorithm is language-independent, we write the steps to demonstrate the logic
behind the solution to be used for solving a problem. But before writing an algorithm, keep the
following points in mind:
 The algorithm should be clear and unambiguous.
 There should be 0 or more well-defined inputs in an algorithm.
 An algorithm must produce one or more well-defined outputs that are equivalent to the
desired output. After a specific number of steps, algorithms must ground to a halt.
 Algorithms must stop or end after a finite number of steps.
 In an algorithm, step-by-step instructions should be supplied, and they should be
independent of any computer code.

Example: Write an algorithm to multiply 2 numbers and print the result

Step 1: Start
Step 2: Input a,b
Step 3: find the product
C= a*b
Step 4: Print c
Step 5: end

Example : Write an algorithm to find the maximum of all the elements present in the array.

Step 1: Start the Program

Step 2: max = A[1]
Step 3: [Compare max with other elements using loop.]
Step 4: If max < A[i]
Assign Max=A[i]
Step 5: If no element is left print max otherwise goto step 3.
Step 6: End

Advantages of Algorithms
 Easy to understand: Since it is a stepwise representation of a solution to a given problem, it
is easy to understand.
 Language Independent: It is not dependent on any programming language, so it can easily
be understood by anyone.
 Debug / Error Finding: Every step is independent / in a flow so it will be easy to spot and fix
the error.
 Sub-Problems: It is written in a flow so now the programmer can divide the tasks which
makes them easier to code.

2
Disadvantages of Algorithms
 Creating efficient algorithms is time-consuming and requires good logical skills.
 Difficult to show branching and looping in algorithms.

1.3 Classification of Algorithms

An Algorithm is a procedure to solve a particular problem in a finite number of steps for a

finite-sized input. The algorithms can be classified in various ways, such as

1. Implementation Method
2. Design Method etc.,

Classification by Implementation Method

1. Recursion or Iteration

A recursive algorithm is an algorithm which calls itself again and again until a base condition is
achieved whereas iterative algorithms use loops and/or data structures like stacks, queues to solve
any problem. Every recursive solution can be implemented as an iterative solution and vice versa.
Example: The Tower of Hanoi is implemented in a recursive fashion while Stock Span problem is
implemented iteratively.

2.Exact or Approximate
Algorithms that are capable of finding an optimal solution for any problem are known as the exact
algorithm. For all those problems, where it is not possible to find the most optimized solution, an
approximation algorithm is used. Approximate algorithms are the type of algorithms that find the
result as an average outcome of sub outcomes to a problem.
Example: For NP-Hard Problems, approximation algorithms are used. Sorting algorithms are the exact
algorithms.

3.Serial or Parallel or Distributed Algorithms

In serial algorithms, one instruction is executed at a time while parallel algorithms are those in
which we divide the problem into subproblems and execute them on different processors. If parallel
algorithms are distributed on different machines, then they are known as distributed algorithms.

Classification by Design Method

There are primarily three main categories into which an algorithm can be named in this type of
classification. They are:

1. Greedy Method
In the greedy method, at each step, a decision is made to choose the local optimum, without
thinking about the future consequences.
Example: Fractional Knapsack, Activity Selection.

2. Divide and Conquer

The Divide and Conquer strategy involves dividing the problem into sub-problem, recursively
solving them, and then recombining them for the final answer.
Example: Merge sort, Quicksort.
3
3. Dynamic Programming
The approach of Dynamic programming is similar to divide and conquer. The difference is that
whenever we have recursive function calls with the same result, instead of calling them again we
try to store the result in a data structure in the form of a table and retrieve the results from the
table. Thus, the overall time complexity is reduced. “Dynamic” means we dynamically decide,
whether to call a function or retrieve values from the table.
Example: 0-1 Knapsack, subset-sum problem.

4. Linear Programming
In Linear Programming, there are inequalities in terms of inputs and maximizing or minimizing
some linear functions of inputs.
Example: Maximum flow of Directed Graph

5. Reduction(Transform and Conquer)

In this method, we solve a difficult problem by transforming it into a known problem for which
we have an optimal solution. Basically, the goal is to find a reducing algorithm whose complexity is
not dominated by the resulting reduced algorithms.
Example: Selection algorithm for finding the median in a list involves first sorting the list and then
finding out the middle element in the sorted list. These techniques are also called transform and
conquer.

6. Backtracking
This technique is very useful in solving combinatorial problems that have a single unique
solution. Where we have to find the correct combination of steps that lead to fulfilment of the
task. Such problems have multiple stages and there are multiple options at each stage. This
approach is based on exploring each available option at every stage one-by-one. While exploring
an option if a point is reached that doesn’t seem to lead to the solution, the program control
backtracks one step, and starts exploring the next option. In this way, the program explores all
possible course of actions and finds the route that leads to the solution.
Example: N-queen problem, maize problem.

7. Branch and Bound

This technique is very useful in solving combinatorial optimization problem that have multiple
solutions and we are interested in find the most optimum solution. In this approach, the entire
solution space is represented in the form of a state space tree. As the program progresses each
state combination is explored, and the previous solution is replaced by new one if it is not the
optimal than the current solution.
Example: Job sequencing, Travelling salesman problem.

1.4 Fundamentals of the Analysis of Algorithm Efficiency

Algorithm Complexity

 Complexity in algorithms refers to the amount of resources (such as time or memory) required
to solve a problem or perform a task.
 The most common measure of complexity is time complexity, which refers to the amount of
time an algorithm takes to produce a result as a function of the size of the input.
 Memory complexity refers to the amount of memory used by an algorithm.
4
  Algorithm designers strive to develop algorithms with the lowest possible time and memory
complexities, since this makes them more efficient and scalable.
The complexity of an algorithm is a function describing the efficiency of the algorithm in terms of the
amount of data the algorithm must process.
Usually there are natural units for the domain and range of this function.
An algorithm is analysed using Time Complexity and Space Complexity. Writing an efficient algorithm
help to consume the minimum amount of time for processing the logic.

Time Complexity and Space Complexity

For algorithm A, it is judged on the basis of two parameters for an input of size n
Time Complexity
Time taken by the algorithm to solve the problem. It is measured by calculating the iteration of
loops, number of comparisons etc.

 Time complexity is a function describing the amount of time an algorithm takes in terms of
the amount of input to the algorithm.
 “Time” can mean the number of memory accesses performed, the number of comparisons
between integers, the number of times some inner loop is executed, or some other natural
unit related to the amount of real time the algorithm will take.

Space Complexity
Space taken by the algorithm to solve the problem. It includes space used by necessary input
variables and any extra space (excluding the space taken by inputs) that is used by the algorithm. For
example, if we use a hash table (a kind of data structure), we need an array to store values so
 this is an extra space occupied, hence will count towards the space complexity of the
algorithm. This extra space is known as Auxiliary Space.
 Space complexity is a function describing the amount of memory(space)an algorithm takes
in terms of the amount of input to the algorithm.
 Space complexity is sometimes ignored because the space used is minimal and/ or obvious,
but sometimes it becomes an issue as time.

Note : The choice of data structure should be based on the time complexity and space complexity of
the operations that will be performed.

Efficiency of algorithms

The way to study the efficiency of an algorithm is to implement it and experiment by running
the program on various test inputs while recording the time spent during each execution.
A simple mechanism in Java is based on use of the currentTimeMillis() method of the System
class for collecting such running times. That method reports the number of milliseconds that have
passed since a benchmark time known as the epoch (January 1, 1970 UTC).
The key is that if we record the time immediately before executing the algorithm and then
immediately after it.

5
long start = System.currentTimeMillis( ); // record the starting time
/∗ (run the algorithm) ∗/
long end = System.currentTimeMillis( ); // record the ending time
long elapsed = end − start; //Total time elapsed
Measuring elapsed time provides a reasonable reflection of an algorithm’s efficiency.
1.5 The Analysis Framework

Efficiency of an algorithm can be measured by time complexity and space complexity. In addition
to that following are key points to measure the efficiency.
1. Measuring an Input’s Size
2. Units for Measuring Running Time
3. Orders of Growth
4. Worst-Case, Best-Case, and Average-Case Efficiencies
1. Measuring an Input’s Size

Almost all algorithms run longer on larger inputs. For example, it takes longer to sort larger
arrays, multiply larger matrices, and so on. Therefore, it is logical to investigate an algorithm’s efficiency
as a function of some parameter n indicating the algorithm’s input size.
In most cases, selecting such a parameter is quite straightforward. For example, it will be the size
of the list for problems of sorting, searching, finding the list’s smallest element, and most other
problems dealing with lists.
For the problem of evaluating a polynomial p(x) = anxn + . . . + a0 of degree n, it will be the
polynomial’s degree or the number of its coefficients, which is larger by 1 than its degree. We can see
from the discussion that such a minor difference is inconsequential for the efficiency analysis.
The choice of a parameter indicating an input size plays a vital role. One such example is
computing the product of two n × n matrices. There are two natural measures of size for this problem.
The first and more frequently used is the matrix order n. But the other natural contender is the total
number of elements N in the matrices being multiplied. (The latter is also more general since it is
applicable to matrices that are not necessarily square.)
Since there is a simple formula relating these two measures, we can easily switch from one to the
other, but the answer about an algorithm’s efficiency will be qualitatively different depending on which
of these two measures we use , The choice of an appropriate size metric can be influenced by
operations of the algorithm in question. For example, how should we measure an input’s size for a spell-
checking algorithm? If the algorithm examines individual characters of its input, we should measure the
size by the number of characters; if it works by processing words, we should count their number in the
input.
We should make a special note about measuring input size for algorithms solving problems such
as checking primality of a positive integer n. Here, the input is just one number, and it is this number’s
magnitude that determines the input size. In such situations, it is preferable to measure size by the
number b of bits in the n’s binary representation:

6
This metric usually gives a better idea about the efficiency of algorithms in question.

2.Units for Measuring Running Time

The next issue concerns units for measuring an algorithm’s running time. Of course, we can
simply use some standard unit of time measurement—a second, or millisecond, and so on—to measure
the running time of a program implementing the algorithm.
There are obvious drawbacks to such an approach, however: dependence on the speed of a
particular computer, dependence on the quality of a program implementing the algorithm and of the
compiler used in generating the machine code, and the difficulty of clocking the actual running time of
the program. Since we are after a measure of an algorithm’s efficiency, we would like to have a metric
that does not depend on these extraneous factors.
One possible approach is to count the number of times each of the algorithm’s operations is
executed. This approach is both excessively difficult and, as we shall see, usually unnecessary. The thing
to do is to identify the most important operation of the algorithm, called the basic operation, the
operation contributing the most to the total running time, and compute the number of times the basic
operation is executed.
As a rule, it is not difficult to identify the basic operation of an algorithm: it is usually the most time-
consuming operation in the algorithm’s innermost loop. For example, most sorting algorithms work by
comparing elements (keys) of a list being sorted with each other; for such algorithms, the basic
operation is a key comparison.
As another example, algorithms for mathematical problems typically involve some or all of the
four arithmetical operations: addition, subtraction, multiplication, and division. Of the four, the most
time-consuming operation is division, followed by multiplication and then addition and subtraction, with
the last two usually considered together.
Thus, the established framework for the analysis of an algorithm’s time efficiency suggests
measuring it by counting the number of times the algorithm’s basic operation is executed on inputs of
size n.
Let cop be the execution time of an algorithm’s basic operation on a particular computer, and
let C(n) be the number of times this operation needs to be executed for this algorithm. Then we can
estimate the running time T (n) of a program implementing this algorithm on that computer by the
formula
T (n) ≈ copC(n).

Of course, this formula should be used with caution. The count C(n) does not contain any information
about operations that are not basic, and, in fact, the count itself is often computed only approximately.
Further, the constant cop is also an approximation whose reliability is not always easy to assess. Still,
unless n is extremely large or very small, the formula can give a reasonable estimate of the algorithm’s
running time. It also makes it possible to answer such questions as “How much faster would this

7
algorithm run on a machine that is 10 times faster than the one we have?” The answer is, obviously, 10
times. Or, assuming that C(n) = 21 n(n − 1), how much longer will the algorithm run if we double its
input size? The answer is about four times longer. Indeed, for all but very small values of n.

Note that we were able to answer the last question without actually knowing the value of cop: it was
neatly cancelled out in the ratio. Also note that 21, the multiplicative constant in the formula for the
count C(n), was also cancelled out. It is for these reasons that the efficiency analysis framework ignores
multiplicative constants and concentrates on the count’s order of growth to within a constant multiple
for large-size inputs.
3.Orders of Growth

A difference in running times on small inputs is not what really distinguishes efficient algorithms
from inefficient ones. When we have to compute, for example, the greatest common divisor of two
small numbers, it is not immediately clear how much more efficient Euclid’s algorithm is compared to
the other algorithms.
It is only when we have to find the greatest common divisor of two large numbers that the
difference in algorithm efficiencies becomes both clear and important. For large values of n, it is the
function’s order of growth that counts: just look at Table 2.1, which contains values of a few functions
particularly important for analysis of algorithms.
The magnitude of the numbers in Table 2.1 has a profound significance for the analysis of
algorithms. The function growing the slowest among these is the logarithmic function. It grows so
slowly, in fact, that we should expect a program

implementing an algorithm with a logarithmic basic-operation count to run practically instantaneously

on inputs of all realistic sizes. Also note that although specific values of such a count depend, of course,
on the logarithm’s base, the formula
loga n = loga b logb n
8
makes it possible to switch from one base to another, leaving the count logarithmic but with a new
multiplicative constant. This is why we omit a logarithm’s base and write simply log n in situations where
we are interested just in a function’s order of growth to within a multiplicative constant.
Algorithms that require an exponential number of operations are practical for solving only problems of
very small sizes.

4.Worst-Case, Best-Case, and Average-Case Efficiencies

It is reasonable to measure an algorithm’s efficiency as a function of a parameter indicating the

size of the algorithm’s input. But there are many algorithms for which running time depends not only on
an input size but also on the specifics of a particular input.
Consider, as an example, sequential search. This is a straightforward algorithm that searches for
a given item (some search key K) in a list of n elements by checking successive elements of the list until
either a match with the search key is found or the list is exhausted.
Best case efficiency

The best-case scenario for an algorithm is the scenario in which the algorithm performs the
minimum amount of work (e.g. takes the shortest amount of time, uses the least amount of memory,
etc.). The best-case efficiency of an algorithm is its efficiency for the best-case input of size n, which is
an input (or inputs) of size n for which the algorithm runs the fastest among all possible inputs of that
size. (Note that the best case does not mean the smallest input; it means the input of size n for which
the algorithm runs the fastest.)

Worst case efficiency

The worst-case scenario for an algorithm is the scenario in which the algorithm performs the
maximum amount of work (e.g. takes the longest amount of time, uses the most amount of memory,
etc.). The worst-case efficiency of an algorithm is its efficiency for the worst-case input of size n, which
is an input (or inputs) of size n for which the algorithm runs the longest among all possible inputs of that
size.

Average case efficiency

The average-case efficiency cannot be obtained by taking the average of the worst-case and the best-
case efficiencies. In average case analysis, we take all possible inputs and calculate the computing time
for all of the inputs. The average case analysis is not easy to do in most practical cases and it is rarely
done. In the average case analysis, we must know (or predict) the mathematical distribution of all
possible inputs.