## 36% off Learn to code by doing. Try hands-on Interview Preparation with Codepect PRO. Claim Discount Now

## INTRODUCTION

## CHAPTER

## 1

## The objective of this chapter is to explain the importance of the analysis of algorithms, their notations, relationships and solving as many problems as possible. Let us first focus on understanding the basic elements of algorithms, the importance of algorithm analysis, and then slowly move toward the other topics as mentioned above. After completing this chapter, you should be able to find the complexity of any given algorithm (especially recursive functions).

## 1.1 Variables

## Before going to the definition of variables, let us relate them to old mathematical equations. All of us have solved many mathematical equations since childhood. As an example, consider the below equation:

## We don’t have to worry about the use of this equation. The important thing that we need to understand is that the equation has names (x and y), which hold values (data). That means the names (x and y) are placeholders for representing data. Similarly, in computer science programming we need something for holding data, and variables is the way to do that.

## 1.2 Data Types

## The Type Of Data That a Variable Can Store are called Data Types .In the above-mentioned equation, the variables x and y can take any values such as integral numbers (10, 20), real numbers (0.23, 5.5), or just 0 and 1. To solve the equation, we 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.

## Computer memory is all filled with zeros and ones. If we have a problem and we want to code it, it’s very difficult to provide the solution in terms of zeros and ones. To help users, programming languages and compilers provide us with data types. For example, integer takes 2 bytes (actual value depends on compiler), float takes 4 bytes, etc. This says that in memory we are combining 2 bytes (16 bits) and calling it an integer. Similarly, combining 4 bytes (32 bits) and calling it a float. A data type reduces the coding effort. At the top level, there are two types of data types:

• System-defined data types (also called Primitive data types)

• User-defined data types

## System-defined data types(primitive data type)

## 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 (-2

15

to 2

15

-1). If it takes 4 bytes (32 bits), then the

possible values are between -2,147,483,648 and +2,147,483,647 (-231to 231-1). The same is the

case with other data types.

## 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. For example, in the snippet below, we are combining many system-defined data types and calling the user defined data type by the name “newType”. This gives more flexibility and comfort in dealing with computer memory

## 1.3 Data Structures

## Data Structure may be defined as the process of storing and organising the data with the various operations.Based on the discussion above, once we have data in variables, we need some mechanism for manipulating that data to solve problems. Data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. A data structure is a special format for organizing and storing data. 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.

## 1.4 Abstract Data Types (ADTs)

## Before defining abstract data types, let us consider the different view of system-defined data types. We all know that, by default, 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. The implementation for these operations can be done when we want to actually use them. That means, 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). An ADT consists of two parts:

1. **Declaration of data**

2. **Declaration of operations**

## Commonly used ADTs include: Linked Lists, Stacks, Queues, Priority Queues, Binary Trees, Dictionaries, Disjoint Sets (Union and Find), Hash Tables, Graphs, and many others. For example, stack uses LIFO (Last-In-First-Out) mechanism while storing the data in data structures. The last element inserted into the stack is the first element that gets deleted. Common operations of it 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.

## While defining the ADTs do not worry about the implementation details. They come into the picture only when we want to use them. Different kinds of ADTs are suited to different kinds of applications, and some are highly specialized to specific tasks. By the end of this book, we will go through many of them and you will be in a position to relate the data structures to the kind of problems they solve.

## 1.5 What is an Algorithm?

## Let us consider the problem of preparing an omelette. To prepare an omelette, we follow the steps given below:

1) Get the frying pan.

2) Get the oil.

a. Do we have oil?

i. If yes, put it in the pan.

ii. If no, do we want to buy oil?

1. If yes, then go out and buy.

2. If no, we can terminate.

3) Turn on the stove, etc…

What we are doing is, for a given problem (preparing an omelette), we are providing a step-bystep procedure for solving it. The formal definition of an algorithm can be stated as:

**An algorithm is the step-by-step unambiguous instructions to solve a given problem**

## In the traditional study of algorithms, there are two main criteria for judging the merits of algorithms: correctness (does the algorithm give solution to the problem in a finite number of steps?) and efficiency (how much resources (in terms of memory and time) does it take to execute the).

**Note**: We do not have to prove each step of the algorithm

## 1.6 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.

## 1.7 Goal of the Analysis of Algorithms

The goal of the analysis of algorithms is to compare algorithms (or solutions) mainly in terms of

running time but also in terms of other factors (e.g., memory, developer effort, etc.)

## 1.8 What is Running Time Analysis?

## It is the process of determining how processing time increases as the size of the problem (input size) increases. Input size is the number of elements in the input, and depending on the problem type, the input may be of different types. The following are the common types of inputs.

Size of an array

• Polynomial degree

• Number of elements in a matrix

• Number of bits in the binary representation of the input

• Vertices and edges in a graph.

## 1.9 How to Compare Algorithms

To compare algorithms, let us define a few objective measures:

**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. This kind of comparison is independent of machine time, programming style, etc.

## 1.10 What is Rate of Growth?

## The rate at which the running time increases as a function of input is called rate of growth. Let us assume that you go to a shop to buy a car and a bicycle. If your friend sees you there and asks what you are buying, then in general you say buying a car. This is because 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).

Total Cost=Cost of car +Cost of Bicycle

Total Cost=Cost of car(approx)

## For the above-mentioned example, we can represent the cost of the car and the cost of the bicycle in terms of function, and for a given function ignore the low order terms that are relatively insignificant (for large value of input size, n). As an example, in the case below, n 4 , 2n 2 , 100n and 500 are the individual costs of some function and approximate to n 4 since n 4 is the highest rate of growth.

n^4+2n^2+100n==n^4

## 1.11 Commonly Used Rates of Growth

The diagram below shows the relationship between different rates of growth.

Highest Rate Of Growth

Rate of Growth is highest after First one

Rate of Growth is highest after Second one

Rate of Growth is highest after Third one

Rate of Growth is highest after Fourth one

Rate of Growth is highest after Fifth one

Rate of Growth is highest after Sixth one

Rate of Growth is highest after Seventh one

Rate of Growth is highest after Eight one

Rate of Growth is highest after Ninth one

Rate of Growth is highest after Tenth one

Rate of Growth is highest after 11th one

Lowest Rate of Growth

## 1.12 Types of Analysis

## To analyze the given algorithm, we need to know with which inputs the algorithm takes less time (performing wel1) and with which inputs the algorithm takes a long time. We have already seen that an algorithm can be represented in the form of an expression. That means we represent the algorithm with multiple expressions: one for the case where it takes less time and another for the case where it takes more 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**

○ 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.

• **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.

Lower Bound <= Average Time <= Upper Bound

For a given algorithm, we can represent the best, worst and average cases in the form of

expressions. As an example, let f(n) be the function which represents the given algorithm.

f(n)=n^2+500 for worst case

f(n)=n^2+100n+500 for best case

Similarly for the average case. The expression defines the inputs with which the algorithm takes

the average running time (or memory)

## 1.13 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 subject of the following discussion. Let us assume that the given algorithm is represented in the form of function f(n).

## 1.14 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.

## Let us see the O–notation with a little more detail. O–notation defined as O(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n > n0}. g(n) is an asymptotic tight upper bound for f(n). 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 /(n).

## Generally we discard lower values of n. That means the rate of growth at lower values of n is not important. In the figure, n0 is the point from which we need to consider the rate of growth for a given algorithm. Below n0 , the rate of growth could be different. n0 is called threshold for the given function.

## Big-O Visualization

O(g(n)) is the set of functions with smaller or the same order of growth as g(n). For example;

O(n2) includes O(1), O(n), O(nlogn), etc.

**Note:** Analyze the algorithms at larger values of n only. What this means is, below n0 we do not

care about the rate of growth.

## Big-O Examples

## 1.15 Omega-Q Notation [Lower Bounding Function]

## Similar to the O discussion, 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) = 100n 2 + 10n + 50, g(n) is Ω(n 2 ).

## 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). 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).

## Ω Examples

## 1.16 Theta-Θ Notation [Order Function]

## This notation decides whether the upper and lower bounds of a given function (algorithm) are the same. The average running time of an algorithm is always between the lower bound and the upper bound. If the upper bound (O) and lower bound (Ω) give the same result, then the Θ notation will also have the same rate of growth.

As an example, let us assume that f(n) = 10n + n is the expression. Then, its tight upper bound

g(n) is O(n). The rate of growth in the best case is g(n) = O(n).

## In this case, the rates of growth in the best case and worst case are the same. As a result, the average case will also be the same. For a given function (algorithm), if the rates of growth (bounds) for O and Ω are not the same, then the rate of growth for the Θ case may not be the same. In this case, we need to consider all possible time complexities and take the average of those (for example, for a quick sort average case, refer to the Sorting chapter).

## Now consider the definition of Θ notation. It is defined as Θ(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).

## Θ Examples

## 1.17 Important Notes

## For analysis (best case, worst case and average), we try to give the upper bound (O) and lower bound (Ω) and average running time (Θ). From the above examples, it should also be clear that, for a given function (algorithm), getting the upper bound (O) and lower bound (Ω) and average running time (Θ) may not always be possible. For example, if we are discussing the best case of an algorithm, we try to give the upper bound (O) and lower bound (Ω) and average running time (Θ).

In the remaining chapters, we generally focus on the upper bound (O) because knowing the lower

bound (Ω) of an algorithm is of no practical importance, and we use the Θ notation if the upper

bound (O) and lower bound (Ω) are the same.

## 1.18 Why is it called Asymptotic Analysis?

## From the discussion above (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.

## 1.19 Guidelines for Asymptotic Analysis

## From the discussion above (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.

## * There are some general rules to help us determine the running time of an algorithm.

## 1.20 Simplyfying properties of asymptotic notations

Transitivity: f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n)). Valid for O and Ω

as well.

• Reflexivity: f(n) = Θ(f(n)). Valid for O and Ω.

• Symmetry: f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n)).

• Transpose symmetry: f(n) = O(g(n)) if and only if g(n) = Ω(f(n)).

• If f(n) is in O(kg(n)) for any constant k > 0, then f(n) is in O(g(n)).

• If f1(n) is in O(g1(n)) andf2(n) is inO(g2(n)),then(f1f2(n) is inO(max(g1(n)),(g1(n))).

• If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)) then f1(n)f2(n) is in O(g1(n) g1(n)).

## 1.21 Commonly used Logarithms and Summations

## Logarithms

## Arithmetic series

## Geometric series

## Harmonic series

## Other important formulae

## 1.22 Master Theorem for Divide and Conquer Recurrenc

## All divide and conquer algorithms (also discussed in detail in the Divide and Conquer chapter) divide the problem into sub-problems, each of which is part of the original problem, and then perform some additional work to compute the final answer. As an example, a merge sort algorithm [for details, refer to Sorting chapter] operates on two sub-problems, each of which is half the size of the original, and then performs O(n) additional work for merging. This gives the running time equation:

The following theorem can be used to determine the running time of divide and conquer

algorithms. For a given program (algorithm), first we try to find the recurrence relation for the

problem. If the recurrence is of the below form then we can directly give the answer without fully

solving it. If the recurrence is of the form , where a ≥ 1,b >

1,k ≥ 0 and p is a real number, then:

## 1.23 Divide and Conquer Master Theorem: Problems & Solutions

For each of the following recurrences, give an expression for the runtime T(n) if the recurrence

can be solved with the Master Theorem. Otherwise, indicate that the Master Theorem does not

apply.

## 1.28 Algorithms Analysis: Problems & Solutions

Solution: Let us try solving this function with substitution.

T(n) = 3T(n – 1)

T(n) = 3(3T(n – 2)) = 3

2T(n – 2)

T(n) = 3

2

(3T(n – 3))

.

.

T(n) = 3

nT(n – n) = 3

nT(0) = 3

n

This clearly shows that the complexity of this function is O(3

n

).

Note: We can use the Subtraction and Conquer master theorem for this problem.

Solution: Let us try solving this function with substitution.

T(n) = 2T(n – 1) – 1

T(n) = 2(2T(n – 2) – 1) – 1 = 2

2T(n – 2) – 2 – 1

T(n) = 2

2

(2T(n – 3) – 2 – 1) – 1 = 2

3T(n – 4) – 2

2 – 2

1 – 2

0

T(n) = 2

nT(n – n) – 2

n–1 – 2

n–2 – 2

n–3

.... 2

2 – 2

1 – 2

0

T(n) =2

n – 2

n–1 – 2

n–2 – 2

n – 3

.... 2

2 – 2

1 – 2

0

T(n) =2

n – (2

n – 1) [note: 2

n–1 + 2

n–2 + ··· + 2

0 = 2

n

]

T(n) = 1

∴ Time Complexity is O(1). Note that while the recurrence relation looks exponential, the

solution to the recurrence relation here gives a different result.

We can define the ‘s’ terms according to the relation si = si–1 + i. The value oft’ increases by 1

for each iteration. The value contained in ‘s’ at the i

th

iteration is the sum of the first ‘(‘positive

integers. If k is the total number of iterations taken by the program, then the while loop terminates

if:

P

The complexity of the above function is O(n

2

logn).

Solution: The recurrence relation for the running time of this program is: T(n) = T(n – 1) + T(n –

2) + c. Note T(n) has two recurrence calls indicating a binary tree. Each step recursively calls the

program for n reduced by 1 and 2, so the depth of the recurrence tree is O(n). The number of

leaves at depth n is 2

n since this is a full binary tree, and each leaf takes at least O(1)

computations for the constant factor. Running time is clearly exponential in n and it is O(2

n

).