LINEAR DATA STRUCTURES

Time Complexity of Algorithms

(Asymptotic Notations)

What is Complexity?
The level of difficulty in solving mathematical
problems are measured by
The time
(time complexity)
memory space required
(space complexity)

Major Factors in Algorithms Design

1. Correctness
An algorithm is said to be correct if
For every input, it halts with correct output.
An incorrect algorithm might not halt at all (or)
It might halt with an answer other than desired one.
Correct algorithm solves a computational problem
2. Algorithm Efficiency
Measuring efficiency of an algorithm,
do its analysis i.e. growth rate.
Compare efficiencies of different algorithms for the same problem.

Complexity Analysis
Algorithm analysis means predicting resources such as
computational time
memory
Worst case analysis
Provides an upper bound on running time
Average case analysis
Provides the expected running time
Very useful, but treat with care
Random (equally likely) inputs
Real-life inputs

Asymptotic Notations Properties

Categorize algorithms based on asymptotic growth rate e.g.
linear, quadratic, exponential
Ignore small constant and small inputs
Estimate upper bound and lower bound on growth rate of
time complexity function
Describe running time of algorithm as n grows to .
Limitations
not always useful for analysis on fixed-size inputs.
All results are for sufficiently large inputs.
Dr Nazir A. Zafar

Advanced Algorithms Analysis

Common Asymptotic Functions

Common Functions we will encounter

Big-Oh

Comment

Constant

O(1)

Cant beat it!

Log log

O(loglogN)

Extrapolation search

Logarithmic O(logN)

Typical time for good searching

algorithms

Linear

O(N)

This is about the fastest that an

algorithm can run given that we need
O(n) just to read the input

N logN

O(NlogN)

Most sorting algorithms

Quadratic

O(N2)

Acceptable when the data size is

small (N<1000)

Cubic

O(N3)

Acceptable when the data size is

small (N<1000)

Only good for really small input sizes

Polynomial time

Increasing cost

Name

Common asymptotic functions

y = x2 + 3x + 5, for x=1..10

y = x2 + 3x + 5, for x=1..20

Common asymptotic functions

Common asymptotic functions

Asymptotic Notations
Asymptotic Notations , O, , o,
We use to mean order exactly,
O to mean order at most,
to mean order at least,
o to mean tight upper bound,
to mean tight lower bound,

Define a set of functions: which is in practice used to

compare two function sizes.

Big-O notation Upper Bound

an

upper

bound

for

the

function f

c*g(n)

n0

Definition:
f(n)

f(n)

Running Time

The big O notation provides

O(g(n))

if

positive

constants c and n0 exist such

that f(n) c g(n) for all n, nn0
e.g. f(n) = 10n2 + 4n + 2
3),
then,
f(n)asymptotic
= O(n2), or O(n
g(n)
is an
upper
O(n4).
bound for f(n).

Input size N

(Omega) notation Lower Bound

lower bound for the function
f

(g(n))

if

positive

constants c and n0 exist such

that f(n) c g(n) for all n, nn0
e.g. f(n) = 10n2 + 4n + 2

then, f(n) = (n2),

(1)

c*g(n)

n0

Definition:
f(n)

f(n)

Running Time

The notation provides a

or (n),

Input size N

 (Theta) Notation Tight Bound

notation is used when

the function f can be bounded

both from above and below by
the same function g
Definition:
f(n)

c2*g(n)
Running Time

The

f(n)
c1*g(n)

n0

(g(n))

if

positive

constants c1and c2, and an n0 exist

such that c1g(n) f(n) c2g(n) for
all n, nn0
e.g. f(n) = 10n2 + 4n + 2

then, f(n) = (n2), and f(n)=O(n2),

therefore, f(n)= (n2)

Input size N

Relations Between , O,

Big-Oh, Theta, Omega

Think of O(f(N)) as less than or equal to f(N)
Upper bound: grows slower than or same rate as f(N)

Think of (f(N)) as greater than or equal to f(N)

Lower bound: grows faster than or same rate as f(N)

Think of (f(N)) as equal to f(N)

Tight bound: same growth rate

(True for large N and ignoring constant factors)

Little-Oh Notation
o-notation is used to denote a upper bound that is not
asymptotically tight.
For a given function g n 0, denoted by o g n the set of functions,

f n : for any positive constants c, there exists a constant no

o g n
such that 0 f n cg n for all n n o

f(n) becomes insignificant relative to g(n) as n

approaches infinity

f n
lim
0
n g n

g(n) is an upper bound for f(n), not asymptotically tight

Little-Omega Notation
Little- notation is used to denote a lower bound
that is not asymptotically tight.

For a given function g n , denote by g n the set of all functions.

g n f n : for any positive constants c, there exists a constant no such that
0 cg n f n for all n n o

f(n) becomes arbitrarily large relative to g(n) as n

approaches infinity

f n
lim

n g n

Comparison of Functions
fg ab
f (n) = O(g(n)) a b
f (n) = (g(n)) a b
f (n) = (g(n)) a = b
f (n) = o(g(n)) a < b
f (n) = (g(n)) a > b

Review:
Other Asymptotic Notations

o() is like <

O() is like
() is like >
() is like
() is like =

Time Complexity of an Algorithm

Time complexity of a given algorithm can be defined for

computation of function f() as a total number of statements that

are executed for computing the value of f(n).
Time complexity is a function dependent from the value of n.
In practice it is often more convenient to consider it as a

function from |n|

Time complexity of an algorithm is generally classified as

three types.
1.

Worst case

2.

Average Case

3.

Best Case

Time Complexity
Worst Case: It is the longest time that an algorithm will use

over all instances of size n for a given problem to produce a

desired result.
Average Case: It is the average time( or average space) that

the algorithm will use over all instances of size n for a given
problem to produce a desired result. It depends on the
probability distribution of instances of the problem.
Best Case: It is the shortest time ( or least space ) that the

algorithm will use over all instances of size n for a given

problem to produce a desired result.

Best, Average, and Worst case complexities

Example: Linear Search Complexity
Best Case : Item found at the beginning: One comparison
Worst Case : Item found at the end: n comparisons
Average Case :Item may be found at index 0, or 1, or 2, . . . or n - 1
Average number of comparisons is: (1 + 2 + . . . + n) / n = (n+1) / 2

Worst and Average complexities of common sorting algorithms

Method

Worst Case

Average Case

Selection sort

n2

n2

Insertion sort

n2

n2

Merge sort

n log n

n log n

Quick sort

n2

n log n

Space Complexity
Space Complexity of a program is the amount of memory

consumed by the algorithm ( apart from input and output, if

required by specification) until it completes its execution.
The way in which the amount of storage space required by an

algorithm varies with the size of the problem to be solved.

The space occupied by the program is generally by the

following:
A fixed amount of memory occupied by the space for the program code
and space occupied by the variables used in the program.

Time Complexity Vs Space Complexity

Achieving both is difficult and we have to make use of the

best case feasible

There is always a trade off between the space and time

complexity
If memory available is large then we need not compensate

on time complexity
If speed of execution is not main concern and the memory

available is less then we cant compensate on space

complexity.

DATA STRUCTURES AND

ALGORITHMS

Introduction to Data Structures

Data is a set of elementary items.
The data structures deal with the study of how the data

is organized in the memory, how efficiently it can be

retrieved and manipulated and the possible ways in
which different data items are logically related.
They can be classified into two types
Primitive data structures
Non primitive data structure.

Introduction to Data Structures

Primitive data structure:
These are data structures that can be manipulated directly by

machine instructions.
In C++ language, the different primitive data structures are int,

float, char, double.

Non primitive data structures:
These are data structures that can not be manipulated directly by

machine instructions.
Arrays, linked lists, files etc., are some of non-primitive data

structures and are classified into linear data structures and nonlinear data structures.

Classification of Data Structures

Major operation
Traversing: Accessing

each record exactly

once so that certain items in the record may be

processed
[ Also known as Visiting the record]
Searching: Finding the location of the record

with a given key value, or finding the locations of

all record which satisfy one or more conditions

Major operation
Inserting : Adding a new element to the list
Deleting : Removing a element from the list
Sorting : Arranging the elements in some type of

order (Ascending / Descending)

Merging : Combining two lists into a single list

Introduction to Abstract Data Types

An abstract data type is a data structure and a collection of functions or

procedures which operate on the data structure

An Example: Collections of items
These collections may be organized in many ways and use many different

program structures to represent them.

An abstract point of view, there will be a few common operations on any

collection. These might include:

create

Create a new collection

add

Add an item to a collection

delete

Delete an item from a collection

find

Find an item matching some criterion in the collection

destroy

Destroy the collection

ARRAY

Linear Arrays
A linear array is a list of a finite number of n

homogeneous data elements ( that is data elements

of the same type) such that
The elements of the arrays are referenced respectively by

an index set consisting of n consecutive numbers

The elements of the arrays are stored respectively in

successive memory locations

Linear Arrays
The number n of elements is called the length or

size of the array.

The index set consists of the integer 1, 2, n
Length or the number of data elements of the array

can be obtained from the index set by

Length = UB LB + 1 where UB is the largest
index called the upper bound and LB is the
smallest index called the lower bound of the arrays

Linear Arrays
Element of an array A may be denoted by
Subscript notation A1, A2, , . , An
Parenthesis notation A(1), A(2), . , A(n)
Bracket notation A[1], A[2], .. , A[n]

The number K in A[K] is called subscript or an index

and A[K] is called a subscripted variable

Representation of Linear Array in Memory

1000
1001
1002
1003
1004
1005

:
Computer Memory

Representation of Linear Array in Memory

Let LA be a linear array in the memory of the computer
LOC(LA[K]) = address of the element LA[K] of the

array LA
The element of LA are stored in the successive memory

cells
Computer does not need to keep track of the address of

every element of LA, but need to track only the address

of the first element of the array denoted by Base(LA)
called the base address of LA

Representation of Linear Array in Memory

LOC(LA[K]) = Base(LA) + w(K LB) where w is

the number of words per memory cell of the array

LA [w is the size of the data type]

Example 1
Find the address for LA[6]
Each element of the array
occupy 1 byte

200

LA[0]

201

LA[1]

202

LA[2]

203

LA[3]

204

LA[4]

205

LA[5]

206

LA[6]

207

LA[7]

LOC(LA[K]) = Base(LA) + w(K lower bound)

LOC(LA[6]) = 200 + 1(6 0) = 206

Example 2
Find the address for LA[15]
Each element of the array
occupy 2 bytes

200

LA[0]

201
202

LA[1]

203
204

LA[2]

205
206

LA[3]

207
LOC(LA[K]) = Base(LA) + w(K lower bound)
LOC(LA[15]) = 200 + 2(15 0) = 230

Representation of Linear Array in Memory

Given any value of K, time to calculate LOC(LA[K]) is same
Given any subscript K one can access and locate

the

content of LA[K] without scanning any other element of LA

A collection A of data element is said to be indexed if any

element of A called Ak, can be located and processed in time

that is independent of K

Traversing Linear Arrays

Traversing

is accessing and processing

element of the data structure exactly once.

Linear Array

each

Traversing Linear Arrays

Traversing is accessing and processing each element of

the data structure exactly once.

Linear Array

Traversing Linear Arrays

Traversing is accessing and processing each element of

the data structure exactly once.

Linear Array

Traversing Linear Arrays

Traversing is accessing and processing each element of

the data structure exactly once.

Linear Array

Traversing Linear Arrays

Traversing is accessing and processing each element of

the data structure exactly once.

Linear Array

Traversing Linear Arrays

Traversing is accessing and processing each element of

the data structure exactly once.

Linear Array

1. Repeat for K = LB to UB
Apply PROCESS to LA[K]
[End of Loop]
2. Exit

for( i=0;i<size;i++)
printf(%d,LA[i]);

Inserting and Deleting

Insertion: Adding an element
Beginning
Middle
End
Deletion: Removing an element
Beginning
Middle
End

Insertion
1

Brown

Brown

Davis

Davis

Johnson

Johnson

Smith

Smith

Wagner

Wagner

Ford

Insert Ford at the End of Array

Insertion
1

Brown

Brown

Brown

Brown

Davis

Davis

Davis

Davis

Johnson

Johnson

Smith

Smith

Johnson

Ford

Wagner

Johnson

Wagner

4
5

Smith

Smith

Wagner

Wagner

Insert Ford as the 3rd Element of Array

Insertion is not Possible without loss of

data if the array is FULL

Insertion Algorithm
INSERT (LA, N , K , ITEM) [LA is a linear array with N

elements and K is a positive integers such that K N. This

algorithm inserts an element ITEM into the K th position in LA]
1. [Initialize Counter] Set J := N
2. Repeat Steps 3 and 4 while J K
3. [Move the Jth element downward ] Set LA[J + 1] := LA[J]
4. [Decrease Counter] Set J := J -1
5 [Insert Element] Set LA[K] := ITEM
6. [Reset N] Set N := N +1;
7. Exit

Deletion
1

Brown

Brown

Davis

Davis

Ford

Ford

Johnson

Johnson

Smith

Smith

Taylor

Taylor

Wagner

Deletion of Wagner at the End of Array

Deletion
1

Brown

Davis

Ford

Ford

Johnson

Johnson

Johnson

Smith

Smith

Taylor

Smith

Taylor

Wagner

Taylor

Wagner

Wagner

Brown

Brown

Ford

Deletion of Davis from the Array

Brown

Ford

Johnson

4
5

Smith

Taylor

Wagner

Deletion
1

Brown

Ford

Johnson

Smith

Taylor

Wagner

7
8

No data item can be deleted from an empty

array

Deletion Algorithm
DELETE (LA, N , K , ITEM) [LA is a linear array with N

elements and K is a positive integers such that K N.

This algorithm deletes Kth element from LA ]
1. Set ITEM := LA[K]
2. Repeat for J = K+1 to N:
[Move the Jth element upward] Set LA[J-1] := LA[J]
3. [Reset the number N of elements] Set N := N - 1;
4. Exit

Multidimensional Array
One-Dimensional Array
Two-Dimensional Array
Three-Dimensional Array

Two-Dimensional Array
A Two-Dimensional m x n array A is a collection of

m.n data elements such that each element is

specified by a pair of integers (such as J, K) called
subscripts with property that
1 J m and 1 K n

The element of A with first subscript J and second

subscript K will be denoted by AJ,K or A[J][K]

2D Arrays
The elements of a 2-dimensional array a is shown as

below

a[0][0]
a[1][0]
a[2][0]

a[0][1]
a[1][1]
a[2][1]

a[0][2]
a[1][2]
a[2][2]

a[0][3]
a[1][3]
a[2][3]

Rows of a 2D Array
a[0][0]
a[1][0]
a[2][0]

a[0][1]
a[1][1]
a[2][1]

a[0][2]
a[1][2]
a[2][2]

a[0][3]
a[1][3]
a[2][3]

row 0
row 1
row 2

Columns of a 2D Array
a[0][0]
a[1][0]
a[2][0]

a[0][1]
a[1][1]
a[2][1]

column 0

a[0][2]
a[1][2]
a[2][2]

a[0][3]
a[1][3]
a[2][3]

column 1 column 2 column 3

2D Array
Let A be a two-dimensional array m x n
The array A will be represented in the memory by

a block of m x n sequential memory location

Programming language will store array A either
Column by Column (Called Column-Major Order) Ex:

Fortran, MATLAB
Row by Row

Java

(Called Row-Major Order) Ex: C, C++ ,

2D Array in Memory
A

Subscript

Subscript

(1,1)

(1,1)

(2,1) Column 1
(3,1)

(1,2)

(1,2)
(2,2)

Column 2

(1,3)

Column 3

(2,3)
(3,3)
(1,4)

(1,3)
(1,4)
(2,1)

(3,2)

Row 1

(2,2)

Row 2

(2,3)
(2,4)

Column 4

(2,4)
Column-Major
Order
(3,4)

(3,1)
(3,2)
(3,3)
Row-Major Order

Row 3

2D Array

LOC(LA[K]) = Base(LA) + w(K -1)

LOC(A[J,K]) of A[J,K]

Column-Major Order

LOC(A[J,K]) = Base(A) + w[m(K-LB) + (J-LB)]

Row-Major Order

LOC(A[J,K]) = Base(A) + w[n(J-LB) + (K-LB)]

2D Array (Row Major)

A5x6

Jth Row

Kth
Column

A[J][K]

LOC(A[J,K]) = Base(A) + w[n(J-LB) + (K-LB)]

2D Array (Column Major)

A5x6

Jth Row

Kth
Column

A[J][K]

LOC(A[J,K]) = Base(A) + w[m(K-LB) + (J-LB)]

2D Array Example
Consider a 25 x 4 array A.
Suppose the Base(A)=200 and w =2.
Suppose the programming stores 2D array using

row-major.
Compute LOC(A[12,3])
LOC(A[J,K]) = Base(A) + w[n(J-LB) + (K-LB)]

LOC(A[12,3]) = 200 + 2[4(12-1) + (3 -1)] = 292

Multidimensional Array
An n-dimensional m1 x m2 x . x mn array B is a collection of

m1.m2mn data elements in which each element is specified

by a list of n integers indices such as K1, K2, ., Kn called
subscript with the property that
1K1m1, 1K2m2, . 1Knmn
The Element B with subscript K1, K2, ,Kn will be denoted by

BK1,K2, ,Kn

or B[K1,K2,.,Kn]

Multidimensional Array
Let C be a n-dimensional array
The length Li of dimension i of C is the number of

elements in the index set

Li = UBi LBi + 1
For a given subscript Ki, the effective index Ei of Ki

is the number of indices preceding Ki in the index set

Ei = Ki LBi

Multidimensional Array
Address LOC(C[K1,K2, ., Kn]) of an arbitrary element of C

can be obtained as
Column-Major Order
Base(C) + w[((((ENLN-1 + EN-1)LN-2) +..+E3)L2+E2)L1+E1]
Row-Major Order
Base(C) + w[( ((E1L2 + E2)L3 + E3)L4 + .. +EN-1)LN +EN]

STACKS

Stacks
A Stack is defined as a special type of data structure where

items are inserted from one end called top of stack and
items are deleted from the same end.
Stack is organized as a Last In First Out(LIFO) data

structure.
Operations performed on Stacks are:
Insert an item into the stack (Store)
Delete an item from the stack (Retrieve)
Display the contents of the stack

Examples in Real Life

Characteristics of a Stack
When you add an element to the stack, you say that you

push it on the stack (it is always done at the top), and if you
delete an element from a stack, you say that you pop it from
the stack (again from the top of the stack).
Since the last item pushed into the stack is always the first

item to be popped from the stack, a stack is also called as a

Last In, First Out or a LIFO structure.
Unlike an array that is static in terms of its size, a stack is a

dynamic data structure.

Characteristics of a Stack
Since the definition of the stack provides for the insertion and

deletion of nodes into it, a stack can grow and shrink

dynamically at runtime.
An ideal implementation of a stack would be a special kind of

linked list in which insertions and deletions can only be done at

the top of the list.

Operations on Stacks
Some of the typical operations performed on stacks are:
create (s)

to create s as an empty stack

push (s, i)
to insert the element i on top of the stack s
pop (s)
to remove the top element of the stack and
to return the removed element as a
function
value.
top (s)
to return the top element of stack(s)
empty(s) to check whether the stack is empty or not.
It returns true if the stack is empty, and
returns false otherwise.

Array implementation of stack

S[1:6]

Pop(S)

Push(S,a) a

Pop(S) a
Pop(S)
Top=1
Pop(S)
Pop(S) pop(S)

Top=1
Push(S,a) a b c
Push(S,b)
Push(S,c) push(S,d)
Push(S,e) push(S,f)

Push(S,g) a

a
e

f
Pop(S)

Top=6

Top=0
e

Top=6 = n
Stack overflow

Pop(S)
Top=0 stack underflow

Top=5

Push and Pop Algorithm

Linked Representation of Stack

Push and Pop operation

Push and Pop operation

Push Linked stack algorithm

Pop Linked stack algorithm