Design and Analysis of Computer Algorithm Lecture 1

Download 1.12 Mb.

Page	9/10
Date	21.10.2021
Size	1.12 Mb.
	#57544

1 2 3 4 5 6 7 8 9 10

notes lec1

Counting Primitive Operations (§3.4)

Theoretical Analysis

Analysis of Algorithm

Uses a high-level description of the algorithm instead of an implementation
Characterizes running time as a function of the input size, n.
Takes into account all possible inputs
Allows us to evaluate the speed of an algorithm independent of the hardware/software environment

Thursday, October 21, 2021

Counting Primitive Operations (§3.4)

Analysis of Algorithm

By inspecting the pseudo code, we can determine the maximum number of primitive/basic operations executed by an algorithm, as a function of the input size

Algorithm arrayMax(A, n)
# operations
currentMax  A[0] 2
for (i =1; in
(i=1 once, i
if A[i]  currentMax then 2(n  1)
currentMax  A[i] 2(n  1)
return currentMax 1
Total 6n 

Thursday, October 21, 2021

Download 1.12 Mb.

Share with your friends:

1 2 3 4 5 6 7 8 9 10

The database is protected by copyright ©ininet.org 2024
send message