Introduction to Design and

Analysis of Algorithms
Dr. Awnish Kumar
Assistant Professor
Computer Science and Engineering Department
National Institute of Technology Agartala
Basic Elements of Programming
• Variables
• Data Types
Basic Elements of Programming
• Variables: placeholders for representing data.
• In computer science programming we need something for holding
data, and variables is the way to do that.
• Data Types: Variables need to relate them to the kind of values they
can take, and data type is the name used in computer science
programming for this purpose.
• A data type in a programming language is a set of data with
predefined values.
• Examples of data types are: integer, floating point, unit number,
character, string, etc.
Data Types: Categories
1. System-defined data types (Primitive data types)
• Data types that are defined by system are called primitive data types.
• The primitive data types provided by many programming languages are: int, float,
char, double, bool, etc.
• The number of bits allocated for each primitive data type depends on the
programming languages, the compiler and the operating system.
• For the same primitive data type, different languages may use different sizes.
Depending on the size of the data types, the total available values (domain) will
also change.
• For example, “int” may take 2 bytes or 4 bytes. If it takes 2 bytes (16 bits), then
the total possible values are minus 32,768 to plus 32,767 (-215 to 215-1).
• If it takes 4 bytes (32 bits), then the possible values are between -2,147,483,648
and +2,147,483,647 (-231 to 231-1).
Data Types: Categories
2. User defined data types
• If the system-defined data types are not enough, then most
programming languages allow the users to define their own data
types, called user – defined data types.
• Good examples of user defined data types are: structures in C/C + +
and classes in Java.
Data Structures
• Data structure is a particular way of storing and organizing data in a
computer so that it can be used efficiently.
• General data structure types include arrays, files, linked lists, stacks,
queues, trees, graphs and so on.
• Depending on the organization of the elements, data structures are
classified into two types:
1. Linear data structures: Elements are accessed in a sequential order but it
is not compulsory to store all elements sequentially. Examples: Linked
Lists, Stacks and Queues.
2. Non – linear data structures: Elements of this data structure are
stored/accessed in a non-linear order. Examples: Trees and graphs.
Abstract Data Types (ADTs)
• All primitive data types (int, float, etc.) support basic operations such
as addition and subtraction. The system provides the
implementations for the primitive data types.
• For user-defined data types we also need to define operations.
• In general, user defined data types are defined along with their
operations.
• To simplify the process of solving problems, we combine the data
structures with their operations and we call this Abstract Data Types
(ADTs).
Abstract Data Types (ADTs)
• An ADT consists of two parts: Declaration of data and Declaration of
operations.
• Commonly used ADTs: Linked Lists, Stacks, Queues, Priority Queues,
Binary Trees, etc..
• Common operations of Stacks are: creating the stack, pushing an
element onto the stack, popping an element from stack, finding the
current top of the stack, finding number of elements in the stack, etc.
Algorithm
• An algorithm is the step-by-step unambiguous instructions to solve a given
problem.
• Why the Analysis of Algorithms?
• To go from city “A” to city “B”, there can be many ways of accomplishing
this: by flight, by bus, by train and also by bicycle. Depending on the
availability and convenience, we choose the one that suits us.
• Similarly, in computer science, multiple algorithms are available for solving
the same problem (for example, a sorting problem has many algorithms,
like insertion sort, selection sort, quick sort and many more).
• Algorithm analysis helps us to determine which algorithm is most efficient
in terms of time and space consumed.
Algorithms: Comparison
• Execution times? Not a good measure as execution times are specific to a
particular computer.
• Number of statements executed? Not a good measure, since the number
of statements varies with the programming language as well as the style of
the individual programmer.
• Ideal solution? Let us assume that we express the running time of a given
algorithm as a function of the input size n (i.e., f(n)) and compare these
different functions corresponding to running times.
• Running Time Analysis: It is the process of determining how processing
time increases as the size of the problem (input size) increases.
• This kind of comparison, i.e., running time analysis, is independent of
machine time, programming style, etc.
Rate of Growth
• The rate at which the running time increases as a function of input is called
rate of growth.
• The cost of the car is high compared to the cost of the bicycle
(approximating the cost of the bicycle to the cost of the car).

• In the case below, n4, 2n2, 100n and 500 are the individual costs of some
function and approximate to n4 since n4 is the highest rate of growth.
Decreasing Order of Rate of Growth
Types of Analysis
• To analyze the given algorithm, we need to know with which inputs
the algorithm takes less time (performing well) and with which inputs
the algorithm takes a long time.
• In general, the first case is called the best case and the second case is
called the worst case for the algorithm.
• To analyze an algorithm we need some kind of syntax, and that forms
the base for asymptotic analysis/notation. There are three types of
analysis:
• Worst case, Best case, and Average case.
Types of Analysis
• Worst case
- Defines the input for which the algorithm takes a long time (slowest
time to complete).
- Input is the one for which the algorithm runs the slowest.
• Best case
- Defines the input for which the algorithm takes the least time (fastest
time to complete).
- Input is the one for which the algorithm runs the fastest.
Types of Analysis
• Average case
- Provides a prediction about the running time of the algorithm.
- Run the algorithm many times, using many different inputs that
come from some distribution that generates these inputs, compute the
total running time (by adding the individual times), and divide by the
number of trials.
- Assumes that the input is random.
Asymptotic Notation
• Having the expressions for the best, average and worst cases, for all
three cases we need to identify the upper and lower bounds.
• To represent these upper and lower bounds, we need some kind of
syntax, and that is the asymptotic notation.
1. Big-O Notation [Upper Bounding Function]
2. Omega – Ω Notation [Lower Bounding Function]
3. Theta - θ Notation [Order Function]
• Let us assume that the given algorithm is represented in the form of
function f(n).
Big-O Notation [Upper Bounding Function]
• This notation gives the tight upper bound
of the given function. Generally, it is
represented as f(n) = O(g(n)).
• That means, at larger values of n, the
upper bound of f(n) is g(n).
• For example, if f(n) = n4 + 100n2 + 10n + 50
is the given algorithm, then n4 is g(n).
• That means g(n) gives the maximum rate of
growth for f(n) at larger values of n.
• O–notation defined as O(g(n)) = {f(n): there
exist positive constants c (c>0) and n0
(n0>=1) such that 0 ≤ f(n) ≤ cg(n) for all n >
n0}. g(n) is an asymptotic tight upper
bound for f(n).
Big-O Notation [Upper Bounding Function]
• Our objective is to give the smallest rate of growth g(n) which is greater than or
equal to the given algorithms’ rate of growth f(n).
• Example-1 Find upper bound for f(n) = 3n + 8.
• Solution: 3n + 8 ≤ 4n, for all n ≥ 8 [0 ≤ f(n) ≤ cg(n) ]
∴ 3n + 8 = O(n) with c = 4 and n0 = 8
• Example-2 Find upper bound for f(n) = n2 + 1
• Solution: n2 + 1 ≤ 2n2, for all n ≥ 1
∴ n2 + 1 = O(n2) with c = 2 and n0 = 1
• Example-3 Find upper bound for f(n) = n4 + 100n2 + 50
• Solution: n4 + 100n2 + 50 ≤ 2n4, for all n ≥ 11
∴ n4 + 100n2 + 50 = O(n4 ) with c = 2 and n0 = 11
Big-O Notation [Upper Bounding Function]
• Example-4 Find upper bound for f(n) = 2n3 – 2n2
• Solution: 2n3 – 2n2 ≤ 2n3, for all n > 1
∴ 2n3 – 2n2 = O(n3 ) with c = 2 and n0 = 1
• Example-5 Find upper bound for f(n) = n
• Solution: n ≤ n, for all n ≥ 1
∴ n = O(n) with c = 1 and n0 = 1
• Example-6 Find upper bound for f(n) = 410
• Solution: 410 ≤ 410, for all n > 1
∴ 410 = O(1) with c = 1 and n0 = 1
Omega – Ω Notation [Lower Bounding
Function]
• This notation gives the tighter lower bound
of the given algorithm and we represent it
as f(n) = Ω(g(n)).
• That means, at larger values of n, the tighter
lower bound of f(n) is g(n). For example, if
f(n) = 100n2 + 10n + 50, g(n) is Ω(n2).
• The Ω notation can be defined as Ω(g(n)) =
{f(n): there exist positive constants c and n0
such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0}.
• g(n) is an asymptotic tight lower bound for
f(n).
Omega – Ω Notation [Lower Bounding Function]
• Our objective is to give the largest rate of growth g(n) which is less
than or equal to the given algorithm’s rate of growth f(n).
• Example-1 Find lower bound for f(n) = 5n2.
• Solution: ∃ c, n0 Such that: 0 ≤ cn2≤ 5n2 ⇒ cn2 ≤ 5n2 ⇒ c = 5 and n0 =
1∴ 5n2 = Ω(n2) with c = 5 and n0 = 1
Theta - θ Notation [Order Function]
• Θ(g(n)) = {f(n): there exist positive constants c1,c2 and n0 such that 0 ≤
c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0}. g(n) is an asymptotic tight bound
for f(n). Θ(g(n)) is the set of functions with the same order of growth
as g(n).
Why is it called Asymptotic Analysis?
• For all three notations: worst case, best case, and average case, we
can easily understand that, in every case for a given function f(n) we
are trying to find another function g(n) which approximates f(n) at
higher values of n.
• That means g(n) is also a curve which approximates f(n) at higher
values of n.
• In mathematics we call such a curve an asymptotic curve. In other
terms, g(n) is the asymptotic curve for f(n). For this reason, we call
algorithm analysis asymptotic analysis.
Guidelines for Asymptotic Analysis
• There are some general rules to help us
determine the running time of an algorithm.
• Loops: The running time of a loop is, at most, the
running time of the statements inside the loop
(including tests) multiplied by the number of
iterations.

• Nested loops: Analyze from the inside out. Total

running time is the product of the sizes of all the
loops.
Guidelines for Asymptotic Analysis
• Consecutive statements: Add the time
complexities of each statement.
Guidelines for Asymptotic Analysis
• If-then-else statements: Worst-case
running time: the test, plus either the
then part or the else part (whichever
is the larger).
Guidelines for Asymptotic Analysis
• Logarithmic complexity: An algorithm is O(logn) if it takes a constant time to
cut the problem size by a fraction (usually by ½). As an example let us consider
the following program:

• If we observe carefully, the value of i is doubling every time. Initially i = 1, in

next step i = 2, and in subsequent steps i = 4,8 and so on.
• Let us assume that the loop is executing some k times. At k-th step 2k = n, and at
(k + 1)-th step we come out of the loop.
• Taking logarithm on both sides, gives
Properties of asymptotic notations
Commonly used Logarithms and Summations
Practice Problems
• What is the running time of the following function?

• Solution: O(n2log n)
Practice Problems
• What is the running time of the following function?

• Solution: O(nlog2n)
Practice Problems
• What is the running time of the following function?

• Solution: O(n)
Practice Problems
• What is the running time of the following function?

• Solution: O(n5)
Practice Problems
• What is the running time of the following function?

• Solution: O(n2)
Practice Problems
• What is the running time of the following function?

• Solution: O(√n)
Practice Problems
• What is the running time of the following function?

• Solution: O(√n)
End of Module 1