Analysis

-
of
Algorithm
4 Y

complexity
Ime complexate
o

Rotation Constant time

Big O
complexity algo
=>
also takes time
#ind sum of 3 numbers
independent > #/p

I
I
Dead (nol numbers ,
not ,
no 3)
.
-
D Size

② Sum = not + noz + nos-0

③ Print Sum-O
-

① step .

Total =
⑤
# its a constant then time
complexity =
lotD
 Find numbers 3-xE[x y) > closed range
-

Sum of N
-
y - x[xy) +
open at y

D Read N .
-
& Create space for N numbers (num) -
O
many times
?
③ for i = 0 to (n-1 => look ,
how

⑪ Read numstil -

Djatios
①sum = -O
how many times ! I

⑤ for i = 0 to (n-1) => loop -

⑪ Sum = Sum + num [i] - Djation .

⑥ Print sum.-D
-
⑦ Stupi ① Ignore constants
Total :
1+ 1 + n + 1 +h

Linear +1 2n +X
=> O(n) < =

time complexib .
 following
complexits Sum of first
#
time
N natural
to (n 2)
for i 0 numbers
-

for j = (i + 1) to (n -

1) = n(n + 1)
-

2
.
do something .
--

ho w many times
i me
-

o . . . -1) neipE)
_
1 -> 23
... (n -
1) -> (n -

2)
2
- 34... (n -

1) > (n 3)
-
-

i = :
(n -

3) ->
( -

2)(2 -
1
2
>
-

(n -
2) -
> (n 1)
-

- ↓
(n 1 + 1)
-

(n I
-
-

Tortal -
2
 As value of
2
) (n)
+
2
=

(m2 -
n)
get larger
2
n2 -n ~ N
① Ignore constants =
> n -
n

② Pick term with

highest power ofm

=> 0 (n2) =quadratic time complexity

.

time complexab of

for i = 0 to (M/2)

for <i to (n 1)
j 1)
-

= +

0 to (2-1)
for 12 =

--
do Somethin--
 Stack
• Stack is a linear data structure.

• Stack is a container of objects.

 Stack operations
• LIFO – Last In First Out

• Elements are added and removed according to LIFO principle.

• Operations are performed with respect to “top” of stack.

Stade Abstract Data Type (ADT)

7
as
-

element stack
push -adds to

pop
a removes element from stuck .

peek get top element without

is Empty removing if

is Full

defines what

operations can be

performed .
operations
&

emltm
· mem
push (10) fush (5)

Ele Lym( *,

top
f-p() => 5 (bx) > 10
=

Empty
Stuck
de
Away
using
20 4 - push
%
5111 >
-

pop

top z
logical size

>
-
stackData
11

"I
-top
-
-

-
- 0 12 3

TI
-

21

Creference to
Throw allocated memor
Exception block)
j
 -
if (is Full (7) Exten ;
Push(element) StuckDath length 1) return;
top
-

- .

- If stack is full then stop.

==
-
>

- Make space at top for new element. - ++ top;

- Store new element and make it topmost element. > stuck Date [tp]
-
elements =

Pop() throw
- If stack is empty then stop. > if (is EmptyK]
-
Ettn-1 -
; appropriate
- Set topmost element as result. > result
-
stackData [tf];
=
Exception
- Remove topmost element and make element below top, the topmost element.
- Return the result. return result
"
-- top ;
>
-

;
IsEmpty()
- If no element stored at top then return true. > if (top
-
-1) return == true ;
Else return false > return fabe
;
-

IsFull()
- If no space left for new element to be stored then return true.
Else return false. if (top == StuckData :
length
-

1) wethon tre;

return false
;
Cheat if string of paranthesis is balanced of

not

*** (() X

) (7) X
h
[3(3)]X
ootfim expression
Evaluate
#

125/
>
23 + 5

↑*** 9
* 5
E
25

Min Stuck Implement m-stacks in an

agroy
.
Max Stuck

Implement two stacks in an away

.

III
top 2
-

topf >
- [
-
 >
-

push
-- pop
>

of stuck
Aplication
>
- O . .
S => function .
calls

>
- Recursive to Iterative algorithm .

>
-

Other algorithms .
 Queue
• Queue is a linear data structure.

• Queue is a container of objects.

 Queue operations
• FIFO – First In First Out

• Elements are added and removed according to FIFO principle.

• Addition of elements are performed at “rear” of queue.

• Elements are removed from “front” of queue.

front front front
↓ ↓
-
to
-
-
510
- 5 -
↑ -
#A
Sear
*
Sear
reas
Empty
enqueue (5)
Queue
enqueue (10)
from
↓-

510
-
↑
rear

front

*
front

ver
Fo Treas
-
↑
rear
dequeue (3
dequere ()
H H
F
10
Refine
Queu
A

neve

vod (nit element);

enqueue

nit dequeue 2) ;

boolean is Empty () :
I

boolean is Full ()
;

3
Queue Array
using
-

de 01 2 3 4
queur
front
- > I E
Esta
11 enquer
-

,
>
- -
1

ear
Year

clas : Queue
implements
public ---

private int [] queue Data ;

private int front ;

int
private Near
;

public ---
(ii + n)S
new it Inb;
queueData =

3
front -1 ;=
wear=-1y
Enqueue(element) throw
- If queue is full then stop. > if (is Falk)
-
Freturn
:
=>
Exception
- Make space at rear for new element. -> + + recu;

- Store new element and make it the rear element. > Date [Gear]
queue
-

Dequeue()
=
,
element

- If queue is empty then stop. > if (is Empty

-

(3) T
return -1 throw
Exception
- Move the front towards rear. > +e front
-

;
- Remove and return the front element as result.
[front] ;
return queue Data
IsEmpty() rear)
- If no elements stored in queue then return true. >
- if (front ==

return true;
Else return false. > return false
-

IsFull()
- If no space left for new element to be stored then return true.
Else return false. if (wear =
=queur
Date length 1)
-

return true;
return fabe;
linear
queue suffers from the problem that
queue
Can be empty and full at the same time
.

12
(5)

it
enqueue
(10)
-

enqueue
(20)
front >*0X2
-
enqueue
= > TRUE
Is Full()
sear >
-

-X
5
+ 2 dequeue
>
()
-

10
dequeue()
>
-

> 20
dequeue
-

TRUE
is Empty () =>

=> TRUE
Is Full()
Solution
-

① after removing the element shift all

In dequere ,
,

of to left place
remainingclements quere by one .

01 2

Be
2
dequere () >
-

front >
-
-1

Near
>
- X 0

if is empts and full

⑧ In dequere ,
we check queue
time If west front & Near
the yes we
at same . ,

③ Circular queue .
 Circular Queue
• Last position of Circular Queue is connected back to first position.
Making a circle.

front > O

·
-

3
wear > -
#X** #
↓
N = 4 O

Incrementing front and 1) % N

#ear
sear = +

wear is
always a
if (wear == N)
0
MOD N
Operation .
rear =
;
-
 front I =
enqueue (5)

· 7 wear
/ enqueue (2)
=

230
2
enqueue (7)
N = 4 throw
(3)
Enqueue queue full
Full 1) exceptio
I de queness => 5
if (fear +
1) % N = = front)
return true
;
enqueu (9)
Enqueue(element)
- If queue is full then stop.
- Make space at rear for new element. > wear
-
= (rear + 1) % quemData. length;
- Store new element and make it the rear element.

Dequeue()
- If queue is empty then stop.
- Move the front towards rear.-

front
> =
(front +
1) % queue Data -

lengthy
- Remove the front element as result.
- Return result.

IsEmpty()
- If no elements stored in queue then return true.
Else return false.

IsFull()
- If no space left for new element to be stored then return true.
Else return false. if (Crear + 13 % queueData ·
lenght == front)
return true
;
 Application of queue
-

① 0 S
.
.
Schedular

② Simulation .

③ other algorithms .

① Implement Queue using stack .

Queue
& Implement Stack using .
 Linear Data Structures

Linked List 0 12

• Need for a linked list?

I
array
node
date net
head
#D D
~ -on

Noc
 Properties of Linked List
• Stores data as a chain of nodes.

• Each node contains data and a pointer to the next node in the chain.

• First node of linked list is pointed by “head”.

When list is empty, head do not point to any node.

• Last node of list points to no node.

 Pros and Cons of Linked List
• Advantages
o Can dynamically grow or shrink is size.
o Efficient in insertion and deletion of elements.

• Disadvantages
o Lookup OR Random access is inefficient.
 Types of Linked List head

• Single linked list (Uni-directional). ITITOSTD

One node keeps track of one neighbour node only.

• Doubly linked list (Bi-directional).

heads
Each node keeps track of two of its neighbours. NADID
• Circular linked list.
Singly Linked List
Traversal

Starting from first element, access each element one at a time, till the last
element.

to reaa
uras
listtreeead
d e empty ---a[i] .
-1)

*
list is empty .
Do
nothing.
list
⑧Non-empty
- Non-empty list .

head In

E- -
10
current
current
-
⑤
>
emply
Singly LinkedList Traversal
- If list is empty then stop.
- Set current to first node of list. head >
-
empty
- while (current is not empty) do ↑
- Process current node.
- Set current to current node’s next. current
- Stop.
Singly LinkedList Traversal (Optimised)
- Set current to first node of list.
- while (current is not empty) do
- Process current node.
- Set current to current node’s next.
- Stop.