UNIT -1
Algorithms, performance analysis- time complexity and space complexity,
Searching: Linear and binary search methods.
Sorting: Bubble sort, selection sort, Insertion sort, Quick sort, Merge sort, Heap sort. Time complexities.
ALGORITHMS
Definition: An Algorithm is a method of representing the step-by-step procedure for
solving a problem. It is a method of finding the right answer to a problem or to a
different problem by breaking the problem into simple cases.
It must possess the following properties:
1. Finiteness: An algorithm should terminate in a finite number of steps.
2. Definiteness: Each step of the algorithm must be precisely (clearly) stated.
3. Effectiveness: Each step must be effective. i.e.; it should be easily
convertible into program statement and can be performed exactly in a finite
amount of time.
4. Generality: Algorithm should be complete in itself, so that it can be used to
solve all problems of given type for any input data.
5. Input/output: Each algorithm must take zero, one or more quantities as input
data and gives one of more output values.
An algorithm can be written in English like sentences or in any
standard representations. The algorithm written in English language is called Pseudo
code.
Example: To find the average of 3 numbers, the algorithm is as shown below.
Step1: Read the numbers a, b, c, and d.
Step2: Compute the sum of a, b, and c.
Step3: Divide the sum by 3.
Step4: Store the result in variable of d.
Step5: End the program.
Development Of An Algorithm
The steps involved in the development of an algorithm are as follows:
Specifying the problem statement.
Designing an algorithm.
Coding.
Debugging
Testing and Validating
Documentation and Maintenance.
Specifying the problem statement: The problem which has to be implemented in to a
program must be thoroughly understood before the program is written. Problem must be
analyzed to determine the input and output requirements of the program.
DS Using C++ Page 1
, Designing an Algorithm: Once the problem is cleared then a solution method for solving
the problem has to be analyzed. There may be several methods available for obtaining the
required solution. The best suitable method is designing an Algorithm. To improve the
clarity and understandability of the program flowcharts are drawn using algorithms.
Coding: The actual program is written in the required programming language with the help
of information depicted in flowcharts and algorithms.
Debugging: There is a possibility of occurrence of errors in program. These errors must be
removed for proper working of programs. The process of checking the errors in the program
is known as ‗Debugging‘.
There are three types of errors in the program.
Syntactic Errors: They occur due to wrong usage of syntax for the statements.
Ex: x=a*%b
Here two operators are used in between two
operands. Runtime Errors : They are determined at the execution
time of the program
Ex: Divide by zero
Range out of bounds.
Logical Errors : They occur due to incorrect usage of instructions in the program. They are
neither displayed during compilation or execution nor cause any obstruction to the program
execution. They only cause incorrect outputs.
Testing and Validating: Once the program is written , it must be tested and then validated.
i.e., to check whether the program is producing correct results or not for different values of
input.
Documentation and Maintenance: Documentation is the process of collecting, organizing
and maintaining, in written the complete information of the program for future references.
Maintenance is the process of upgrading the program, according to the changing
requirements.
PERFORMANCE ANALYSIS
When several algorithms can be designed for the solution of a problem, there arises
the need to determine which among them is the best. The efficiency of a program or an
algorithm is measured by computing its time and/or space complexities.
The time complexity of an algorithm is a function of the running time of the
algorithm.
The space complexity is a function of the space required by it to run to completion.
The time complexity is therefore given in terms of frequency count.
Frequency count is basically a count denoting number of times a statement execution
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 notations we can give time complexity as ―fastest possible‖,
―slowest possible‖ or ―average time‖.
Various notations such as Ω, θ, O used are called asymptotic notions.
DS Using C++ Page 2
, Big Oh Notation
Big Oh notation denoted by ‗O‘ is a method of representing the upper bound of
algorithm‘s running time. Using big oh notation we can give longest amount of time
taken by the algorithm to complete.
Definition:
Let, f(n) and g(n) are two non-negative functions. And if there exists an integer n0 and
constant C such that C > 0 and for all integers n > n0, f(n) ≤ c*g(n), then
f(n) = Og(n).
Various meanings associated with big-oh are
O(1) constant computing time
O(n) linear
2
O(n ) quadratic
O(n3) cubic
n
O(2 ) exponential
O(logn) logarithmic
The relationship among these computing time is
O(1)< O(logn)< O(n)< O(nlogn)< O(n2)< O(2n)
Omega Notation:-
Omega notation denoted ‗Ω‘ is a method of representing the lower bound of
algorithm‘s running time. Using omega notation we can denote shortest amount of time
taken by algorithm to complete.
Definition:
Let, f(n) and g(n) are two non-negative functions. And if there exists an integer n0
and constant C such that C > 0 and for all integers n > n0, f(n) >c*g(n), then
f(n) = Ω g(n).
Page 3
DS Using C++ Page 3
, Theta Notation:-
Theta notation denoted as ‗θ‘ is a method of representing running time between
upper bound and lower bound.
Definition:
Let, f(n) and g(n) are two non-negative functions. There exists positive constants C1
and C2 such that C1 g(n) ≤ f(n) ≤ C2 g(n) and f(n) = θ g(n)
How to compute time complexity
1 Algorithm Message(n) 0
2 { 0
3 for i=1 to n do n+1
4 { 0
5 write(―Hello‖); n
6 } 0
7 } 0
total frequency count 2n+1
While computing the time complexity we will neglect all the constants, hence ignoring 2
and 1 we will get n. Hence the time complexity becomes O(n).
f(n) = Og(n).
i.e f(n)=O(2n+1)
=O(n) // ignore constants
1 Algorithm add(A,B,m,n) 0
2 { 0
3 for i=1 to m do m+1
4 for j=1 to n do m(n+1)
5 C[i,j] = A[i,j]+B[i,j] mn
DS Using C++ Page 4
Algorithms, performance analysis- time complexity and space complexity,
Searching: Linear and binary search methods.
Sorting: Bubble sort, selection sort, Insertion sort, Quick sort, Merge sort, Heap sort. Time complexities.
ALGORITHMS
Definition: An Algorithm is a method of representing the step-by-step procedure for
solving a problem. It is a method of finding the right answer to a problem or to a
different problem by breaking the problem into simple cases.
It must possess the following properties:
1. Finiteness: An algorithm should terminate in a finite number of steps.
2. Definiteness: Each step of the algorithm must be precisely (clearly) stated.
3. Effectiveness: Each step must be effective. i.e.; it should be easily
convertible into program statement and can be performed exactly in a finite
amount of time.
4. Generality: Algorithm should be complete in itself, so that it can be used to
solve all problems of given type for any input data.
5. Input/output: Each algorithm must take zero, one or more quantities as input
data and gives one of more output values.
An algorithm can be written in English like sentences or in any
standard representations. The algorithm written in English language is called Pseudo
code.
Example: To find the average of 3 numbers, the algorithm is as shown below.
Step1: Read the numbers a, b, c, and d.
Step2: Compute the sum of a, b, and c.
Step3: Divide the sum by 3.
Step4: Store the result in variable of d.
Step5: End the program.
Development Of An Algorithm
The steps involved in the development of an algorithm are as follows:
Specifying the problem statement.
Designing an algorithm.
Coding.
Debugging
Testing and Validating
Documentation and Maintenance.
Specifying the problem statement: The problem which has to be implemented in to a
program must be thoroughly understood before the program is written. Problem must be
analyzed to determine the input and output requirements of the program.
DS Using C++ Page 1
, Designing an Algorithm: Once the problem is cleared then a solution method for solving
the problem has to be analyzed. There may be several methods available for obtaining the
required solution. The best suitable method is designing an Algorithm. To improve the
clarity and understandability of the program flowcharts are drawn using algorithms.
Coding: The actual program is written in the required programming language with the help
of information depicted in flowcharts and algorithms.
Debugging: There is a possibility of occurrence of errors in program. These errors must be
removed for proper working of programs. The process of checking the errors in the program
is known as ‗Debugging‘.
There are three types of errors in the program.
Syntactic Errors: They occur due to wrong usage of syntax for the statements.
Ex: x=a*%b
Here two operators are used in between two
operands. Runtime Errors : They are determined at the execution
time of the program
Ex: Divide by zero
Range out of bounds.
Logical Errors : They occur due to incorrect usage of instructions in the program. They are
neither displayed during compilation or execution nor cause any obstruction to the program
execution. They only cause incorrect outputs.
Testing and Validating: Once the program is written , it must be tested and then validated.
i.e., to check whether the program is producing correct results or not for different values of
input.
Documentation and Maintenance: Documentation is the process of collecting, organizing
and maintaining, in written the complete information of the program for future references.
Maintenance is the process of upgrading the program, according to the changing
requirements.
PERFORMANCE ANALYSIS
When several algorithms can be designed for the solution of a problem, there arises
the need to determine which among them is the best. The efficiency of a program or an
algorithm is measured by computing its time and/or space complexities.
The time complexity of an algorithm is a function of the running time of the
algorithm.
The space complexity is a function of the space required by it to run to completion.
The time complexity is therefore given in terms of frequency count.
Frequency count is basically a count denoting number of times a statement execution
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 notations we can give time complexity as ―fastest possible‖,
―slowest possible‖ or ―average time‖.
Various notations such as Ω, θ, O used are called asymptotic notions.
DS Using C++ Page 2
, Big Oh Notation
Big Oh notation denoted by ‗O‘ is a method of representing the upper bound of
algorithm‘s running time. Using big oh notation we can give longest amount of time
taken by the algorithm to complete.
Definition:
Let, f(n) and g(n) are two non-negative functions. And if there exists an integer n0 and
constant C such that C > 0 and for all integers n > n0, f(n) ≤ c*g(n), then
f(n) = Og(n).
Various meanings associated with big-oh are
O(1) constant computing time
O(n) linear
2
O(n ) quadratic
O(n3) cubic
n
O(2 ) exponential
O(logn) logarithmic
The relationship among these computing time is
O(1)< O(logn)< O(n)< O(nlogn)< O(n2)< O(2n)
Omega Notation:-
Omega notation denoted ‗Ω‘ is a method of representing the lower bound of
algorithm‘s running time. Using omega notation we can denote shortest amount of time
taken by algorithm to complete.
Definition:
Let, f(n) and g(n) are two non-negative functions. And if there exists an integer n0
and constant C such that C > 0 and for all integers n > n0, f(n) >c*g(n), then
f(n) = Ω g(n).
Page 3
DS Using C++ Page 3
, Theta Notation:-
Theta notation denoted as ‗θ‘ is a method of representing running time between
upper bound and lower bound.
Definition:
Let, f(n) and g(n) are two non-negative functions. There exists positive constants C1
and C2 such that C1 g(n) ≤ f(n) ≤ C2 g(n) and f(n) = θ g(n)
How to compute time complexity
1 Algorithm Message(n) 0
2 { 0
3 for i=1 to n do n+1
4 { 0
5 write(―Hello‖); n
6 } 0
7 } 0
total frequency count 2n+1
While computing the time complexity we will neglect all the constants, hence ignoring 2
and 1 we will get n. Hence the time complexity becomes O(n).
f(n) = Og(n).
i.e f(n)=O(2n+1)
=O(n) // ignore constants
1 Algorithm add(A,B,m,n) 0
2 { 0
3 for i=1 to m do m+1
4 for j=1 to n do m(n+1)
5 C[i,j] = A[i,j]+B[i,j] mn
DS Using C++ Page 4
