Algorithm

In Data Structures

Shital Dinde
Definition
• The word Algorithm means ” A set of finite rules or instructions to be
followed in calculations or other problem-solving operations ”
What is the need for algorithms?
• Algorithms are necessary for solving complex problems efficiently and
effectively.
• They help to automate processes and make them more reliable,
faster, and easier to perform.
• Algorithms also enable computers to perform tasks that would be
difficult or impossible for humans to do manually.
• They are used in various fields such as mathematics, computer
science, engineering, finance, and many others to optimize processes,
analyze data, make predictions, and provide solutions to problems.
Characteristics of an Algorithm
Properties of Algorithm
• It should terminate after a finite time.
• It should produce at least one output.
• It should take zero or more input.
• It should be deterministic means giving the same output for the same
input case.
• Every step in the algorithm must be effective i.e. every step should do
some work.
How to Design an Algorithm
• To write an algorithm, the following things are needed as a pre-
requisite:
• The problem that is to be solved by this algorithm i.e. clear problem
definition.
• The constraints of the problem must be considered while solving the
problem.
• The input to be taken to solve the problem.
• The output is to be expected when the problem is solved.
• The solution to this problem is within the given constraints.
Pseudo code
• Pseudo code is an English-like representation of the algorithm logic. It
is part English, part structured code.
• Pseudo code contains algorithm header and statement constructs
• The English part provides a relaxed syntax that describes what must
be done without showing unnecessary details such as error messages.
• The code part consists of an extended version of the basic algorithmic
constructs—sequence, selection, and iteration.
Step 1: Algorithm Header
• Each algorithm begins with a header that names it, purpose of
algorithm, lists its parameters, and describes any preconditions and
postconditions.
• This information is important because it serves to document the
algorithm.
• Therefore, the header information must be complete enough to
communicate to the programmer everything he or she must know to
write the algorithm.
• Purpose
• The purpose is a short statement about what the algorithm does.
• It needs to describe only the general algorithm processing.
• It should not attempt to describe all of the processing.
• Conditions
• The precondition lists any precursor requirements for the parameters.
• Sometimes there are no preconditions, in which case we still list the precondition
with a statement that nothing is required
• The postcondition identifies any action taken and the status of any output
parameters.
• Return
• If a value is returned, it is identified by a return condition. Often there is none, and
no return condition is needed.
Example
Statement Constructs
• Algorithm could be written using only three programming constructs:
sequence, selection, and loop.
• Pseudo code contains only these three basic constructs.
• The implementation of these constructs relies on the richness of the
implementation language.
• For example, the loop can be implemented as a while, do...while, or
for statement in the C language.
• Sequence
• A sequence is one or more statements that do not alter the execution path
within an algorithm.
• Selection
• A selection statement evaluates a condition and executes zero or more
alternatives.
• The results of the evaluation determine which alternates are taken.
• The typical selection statement is the two-way selection as implemented in an
if statement.
• The parts of the selection are identified by indentation
• Loop
• A loop statement iterates a block of code.
• The loop that we use in our pseudocode closely resembles the while loop.
• It is a pretest loop; that is, the condition is evaluated before the body of the
loop is executed.
• If the condition is true, the body is executed. If the condition is false, the loop
terminates.
Example
Advantages of Algorithms
• It is easy to understand.
• An algorithm is a step-wise representation of a solution to a given
problem.
• In an Algorithm the problem is broken down into smaller pieces or
steps hence, it is easier for the programmer to convert it into an
actual program.
Disadvantages of Algorithms
• Writing an algorithm takes a long time so it is time-consuming.
• Understanding complex logic through algorithms can be very difficult.
• Branching and Looping statements are difficult to show in Algorithms.
Algorithm Efficiency
• An algorithm’s efficiency is referred to as the number of
computational resources used by the algorithm.
• There are two main measures for the efficiency of an algorithm.
• space efficiency - It is the amount of memory required by an algorithm until it
completes its execution, also called, space complexity
• time efficiency - The total time needed to complete the execution of an
algorithm is called time complexity, also called time complexity
• Time requirements can be defined as the numerical function T(num), where T(num) can
be measured as the number of steps, provided each step consumes constant time.
• the algorithm’s efficiency as a function of the number of elements to
be processed. The general format is f(n) = efficiency
• Linear Loops loop. We want to know how many times the body of the loop is
repeated in the following code.
• Logarithmic Loops: In a logarithmic loop, the controlling variable is multiplied
or divided in each iteration.
• Nested Loops:
• Loops that contain loops are known as nested loops.
• The total is then the product of the number of iterations in the inner loop and the
number of iterations in the outer loop.
1. Linear Logarithmic : The inner loop in the following code is a loop that multiplies. To see
the multiply loop, look at the update expression in the inner loop.
2. Quadratic: In a quadratic loop, the number of times the inner loop executes
is the same as the outer loop.
3. Dependent Quadratic: In a dependent quadratic loop, the number of
iterations of the inner loop depends on the outer loop.
Big-O Notation
• The number of statements executed in the function for n elements of
data is a function of the number of elements, expressed as f (n).
• Although the equation derived for a function may be complex, a
dominant factor in the equation usually determines the order of
magnitude of the result.
• Therefore, we don’t need to determine the complete measure of
efficiency, only the factor that determines the magnitude.
• This factor is the big-O, as in “on the order of,” and is expressed as
O(n)—that is, on the order of n.
• This simplification of efficiency is known as big-O analysis.
• The big-O notation can be derived from f (n) using the following steps:
• In each term, set the coefficient of the term to 1.
• Keep the largest term in the function and discard the others. Terms are
ranked from lowest to highest as shown below.

logn n nlogn n2 n3 ... nk 2n n!