Prof. N.

Guruprasad UNIT 1 - INTRODUCTION 1

 UNIT 1
Introduction

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 2

 Coverage

1) Introduction to DS and Characteristics

2) Types of Data Structures and its operations
3) Algorithm & its efficiency
4) Prime numbers
5) Input size and running time
6) Asymptotic Notations

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 3

 Introduction to DATA
STRUCTURES

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 4

 • Defined as the group of data elements which provides an
efficient way of storing and organising data in the computer so
that it can be used efficiently.

• Widely used in almost every aspect of Computer Science

• Main part of many computer science algorithms

• Data structures are the building blocks of any program or the

software.

• Choosing the appropriate data structure for a program is the

most difficult task for a programmer.

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 5

 Characteristics:

1) Depicts logical representation of data in computer

memory
2) Depicts logical relationship between various data
elements
3) Helps in efficient management of data elements
4) Allows programmers to process the data in an
efficient manner
Prof. N. Guruprasad UNIT 1 - INTRODUCTION 6
 Types of
DATA STRUCTURES

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 7

 DATA STRUCTURES

PRIMITIVE NON PRIMITIVE

int
LINEAR NON LINEAR

float
Arrays

char Stacks Trees Graphs

Queues

Linked
List

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 8

 Data Structure Operations:

1) Traversing
2) Insertion
3) Deletion
4) Searching
5) Sorting
6) Merging

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 9

 ALGORITHMS

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 10

 Definition
Characteristics
1) Unambiguous
2) Input
3) Output
4) Finiteness
5) Feasibility
6) Independent

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 11

 Good algorithm is like a knife – does exactly what it
is suppose to with minimum efforts.

Using wrong algorithm is like trying to cut a steak

with a screw driver.

You may obtain a result, but would have spent

more effort.

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 12

 Representation of algorithm

1) There are no well-defined standards

2) never written to support a particular programming code.
3) common constructs can be used to write an algorithm.
4) we should know the problem domain

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 13

 General Conventions:

1) Provide valid name for the algorithm.

2) Specify line number.
3) Begin identifier with English alphabet.
4) Not necessary to specify data type
5) Indent the statements inside a block
6) Use read and write
7) End the control structures appropriately

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 14

 Algorithm: to calculate average of 15 numbers

Step 1: BEGIN
Step 2: Set avg=0.0 and sum=0
Step 3: for i = 1 to 15 do
Step 4: read (a)
Step 5: sum = sum + a
Step 6: end – for step 3
Step 7: avg = sum / 15
Step 8: write avg
Step 9: END

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 15

 ALGORITHM EFFICIENCY

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 16

 The efficiency of algorithm depends on two factors :
1) Space efficiency
2) Time efficiency

Components affecting time efficiency:

i) Speed of the computer
ii) Choice of programming language
iii) Compiler used
iv) Choice of algorithm
v) Number of inputs / outputs
vi) Size of inputs / outputs

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 17

 n log2n n n log2n n2 N3 2n N!

10 3.3 101 3.3 * 101 102 103 103 3.6 * 106

102 6.6 102 6.6 * 102 104 106 1.3 * 1030 9.3 * 10157

103 10 103 1 * 104 106 109

104 13 104 1.3 * 105 108 1012

105 17 105 1.7 * 106 1010 1015

106 20 106 2 * 107 1012 1018 Very high

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 18

 Prime numbers

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 19

 Sieve of Eratosthenes

One of the oldest and simplest yet interesting algorithm that

involves arbitrary large data is the sieve of Eratosthene.

Eratosthene (Cyrene circa 284 BC - Alexandria circa 192 BC)

was a great greek mathematician

He was the very first to accurately compute the circumference

of Earth, and he invented this clever algorithm to find prime
numbers.

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 20

 Sieve of Eratosthenes - algorithm

1) Create a list of consecutive integers from two to n, (2, 3, 4,

..., n).
2) Initially, let p equal 2, the first prime number.
3) Strike from the list all multiples of p less than or equal to n.
4) Find the first number remaining on the list greater than p
(this number is the next prime); replace p with this
number.
5) Repeat steps 3 and 4 until p2 is greater than n.
6) All the remaining numbers on the list are prime.

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 21

 Ex: find all prime numbers upto 50

2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 22

 Step 1) p=2 - the first prime number.
Strike from the list all multiples of 2 less
than or equal to n. (i.e 50)

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 23

 Ex: find all prime numbers upto 50

2 3 5 7 9

11 13 15 17 19

21 23 25 27 29

31 33 35 37 39

41 43 45 47 49

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 24

 Step 2) next available number is p=3.

p2=9 (less than n – so proceed)

Keep 3 and strike from the list all

multiples of 3 less than or equal to n. (i.e
50)

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 25

 Ex: find all prime numbers upto 50

2 3 5 7

11 13 17 19

23 25 29

31 35 37

41 43 47 49

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 26

 Step 3) next available number is p=5.

p2=25 (less than n – so proceed)

Keep 5 and strike from the list all

multiples of 5 less than or equal to n. (i.e
50)

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 27

 Ex: find all prime numbers upto 50

2 3 5 7

11 13 17 19

23 29

31 37

41 43 47 49

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 28

 Step 4) next available number is p=7.

p2=49 (less than n – so proceed)

Keep 7 and strike from the list all

multiples of 7 less than or equal to n. (i.e
50)

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 29

 Ex: find all prime numbers upto 50

2 3 5 7

11 13 17 19

23 29

31 37

41 43 47

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 30

 Step 5) next available number is p=11.

p2=121 (not less than n – so stop)

Existing Numbers are PRIME

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,

43 & 47

are prime numbers upto 50

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 31

 Do you know the largest prime number ?

Paul Erdos said

– God may not play dice with the universe, but

something strange is going on with the prime
numbers. [Referring to Albert Einstein's famous belief
that "God does not play dice with the universe."]

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 32

 As of Feb 2024:

The largest known prime is :

282,589,933 − 1
found by Patrick Laroche of Great Internet Mersenne
Prime Search (GIMPS)

This number is 24,862,048 digits long

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 33

 Measuring input size:

almost all algorithms run longer on larger inputs.

operations on larger arrays, matrix multiplication of larger

dimension

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 34

 Units for Measuring running time:

some standard unit of time measurement - a second, or

millisecond, and so on

count the number of times each of the algorithm’s

operations is executed.

basic operation - the operation contributing the most to

the total running time, and compute the number of times
the basic operation is executed.

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 35

 Orders of growth:

way how execution time of a program changes

order of growth - behavior of some algorithms changes

with increase value of n

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 36

 n log2n n n log2n n2 N3 2n N!

10 3.3 101 3.3 * 101 102 103 103 3.6 * 106

102 6.6 102 6.6 * 102 104 106 1.3 * 1030 9.3 * 10157

103 10 103 1 * 104 106 109

104 13 104 1.3 * 105 108 1012

105 17 105 1.7 * 106 1010 1015

106 20 106 2 * 107 1012 1018 Very high

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 37

 from lowest to highest:

2 3 n
1 < log n < n < n log n < n < n < 2 < n!

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 38

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

Will the algorithm efficiency depends on the size of

algorithm’s input alone?

Ex: linear (sequential) search

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 39

 Worst Case – the efficiency of an algorithm for the input of
size n for which the algorithm takes longest time to execute
among all possible inputs.

Best Case – the efficiency of an algorithm for the input of

size n for which the algorithm takes least time to execute
among all possible inputs.

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 40

 ASYMPTOTIC NOTATIONS

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 41

 Coverage

• Asymptotic Notations are the expressions that

are used to represent the complexity of an
algorithm.

1) Best Case
2) Worst Case
3) Average Case

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 42

 What is Asymptotic Behaviour

The word Asymptotic means approaching a value or

curve arbitrarily closely (i.e., as some sort of limit is
taken).

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 43

 To compare the order of the growth scientists use the
following notations :
1) O ( Big Oh )
2) Ω ( Big Omega )
3) Θ ( Big Theta )

Assumptions :
f(n)  algorithms running time
c(n)  basic operation count
g(n)  some simple function to compare with

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 44

 Big Oh notation:

used to define the upper bound of an algorithm in terms of

Time Complexity.

Consider function f(n) as time complexity of an algorithm

and g(n) is the most significant term.

If f(n) <= C g(n) for all n >= n0, C > 0 and n0 >= 1.

Then we can represent f(n) as O(g(n)).

f(n) = O(g(n))

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 45

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 46
 • The function g(n) is normally expressed using higher
order terms of f(n). That is achieved using the
following steps:

1) Take the lower order term of f(n), replace the

constant with next higher order variable. Repeat this
step till we get the higher order term and call it as
c.g(n)
2) Once the constraint f(n) ≤ c g(n) for n ≥ n0 is obtained
we say that f(n) ∈ O(g(n))

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 47

 Ex : Let f(n) = 100 n + 5. Express t(n) using Big Oh.
Solution:
We have f(n) = 100n+5
Replacing 5 with n (so that next higher order term is
obtained)
Call it as C.g(n)

C.g(n) = 100 n + n for n = 5

= 101 n for n = 5

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 48

 Now the following constraint is satisfied .

f(n) ≤ c * g(n) for n ≥ n0

100 n + 5 ≤ 101 * n for n ≥ 5

It is clear that c=101 and g(n)=n and no=5

So by definition - f(n) ∈ O(g(n))

i.e f(n) ∈ O(n)

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 49

 Ex: Let f(n) = 6*2n + n2. Express f(n) using BIG-OH

Solution:

We have f(n) = 6*2n + n2.

Replacing n2. with 2n (to get higher order term)

We get: 6*2n + 2n call it as c.g(n)

c g(n) = 6*2n + 2n = 7*2n for n=4 ( since 2n ≥ n2 for all n ≥ 4)

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 50

 Now the following constraint is satisfied .

f(n) ≤ c . g(n) for n ≥ no

6*2n + n2 ≤ 7 * 2n for n ≥ 4

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 51

 It is clear that c=7 and g(n)=2n and no=4

So by definition - f(n) ∈ O(g(n))

i.e f(n) ∈ O(2n)

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 52

 Big Omega notation:

Big Ω notation, on the other hand, is used to describe the best

case running time for a given algorithm.

f(n) = Ω g(n)

such that there exists a positive constant c and non-negative

integer n0 satisfying the constraint

f(n) ≥ c * g(n) for all n ≥ n0

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 53

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 54
 Example: Let f(n) = 100n+5. Express f(n) using BIG-
OMEGA

Solution:

The constraint to be satisfied is

f(n) ≥ c * g(n) for n ≥ n0

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 55

 f(n) ≥ c * g(n) for n ≥ no

100n + 5 ≥ 100 n for n ≥ 0

It is clear from the above relations that c=100, g(n)=n and

n0=0

So by definition f(n) = Ω g(n)

HENCE f(n) = Ω(n)

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 56
 Example: Let f(n) = 10n3+5. Express f(n) using BIG-
OMEGA

ANSWER:

The constraint to be satisfied is

f(n) ≥ c * g(n) for n ≥ n0

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 57

 f(n) ≥ c * g(n) for n ≥ no

10n3 + 5 ≥ 10 * n3 for n ≥ 0

It is clear from the above relations that c=10, g(n)=n3 and

n0=0

So by definition f(n) = Ω g(n)

HENCE f(n) = Ω(n3)

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 58

 BIG THETA Notation (ϴ)

The function f(n) is said to be big theta of g(n) and

denoted by

f(n) = ϴ g(n)

and there exists some positive constants c1 and c2

and non-negative integer n0 satisfying the constraint:

c1*g(n) ≤ f(n) ≤ c2*g(n) for n ≥ n0

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 59

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 60
 Example: Let f(n) = 10n3+5. Express f(n) using BIG-
THETA

ANSWER:

The constraint to be satisfied is

c1*g(n) ≤ f(n) ≤ c2*g(n) for n ≥ n0

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 61

 c1 * g(n) ≤ f(n) ≤ c2 * g(n) for n ≥ n0

10 * n3 ≤ 10 * n3 + 5 ≤ 11 * n3 for n ≥ 2

It is clear from the above relations that c1=10, c2=11,

n0=2 and g(n)=n3

So by definition f(n) = ϴ g(n)

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 62

 Example: Let f(n) = 6 * 2n + n2 . Express f(n) using
BIG-THETA

ANSWER:

The constraint to be satisfied is

c1*g(n) ≤ f(n) ≤ c2*g(n) for n ≥ n0

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 63

 c1 * g(n) ≤ f(n) ≤ c2 * g(n) for n ≥ n0

6 * 2n ≤ 6 * 2n + n2 ≤ 7 * 2n for n ≥ 4

It is clear from the above relations that c1=6, c2=7,

n0=4 and g(n)=2n

So by definition f(n) = ϴ g(2n)

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 64

 ANY DOUBTS?

Prof. N. Guruprasad UNIT 1 - INTRODUCTION 65