Data Structure and

Algorithm Analysis
What We Cover
Analysis of Algorithms: worst case time and space
complexity
Data Structures: stack, queue, linked list, tree,
priority queue, heap, and hash;
Searching algorithms: binary and AVL search
trees;
Sorting algorithms: merge sort, quick sort, bucket
sort and radix sort;
Graph: data structure, depth first search and
breadth first search. (add some interesting
contents).

04/29/25 2
Why This Course?
You will be able to evaluate the quality of
a program (Analysis of Algorithms:
Running time and memory space )
You will be able to write fast programs
You will be able to solve new problems
You will be able to give non-trivial
methods to solve problems.
(Your algorithm (program) will be faster than
others.)
04/29/25 3
Data Structures: A systematic way of
organizing and accessing data.
--No single data structure works well for ALL purposes.

Input Algorithm Output

An algorithm is a step-by-step
procedure for
solving a problem in a finite amount of
Algorithm Descriptions
Nature languages: Chinese, English, etc.
Pseudo-code: codes very close to computer
languages, e.g., C programming language.
Programs: C programs, C++ programs, Java
programs.

Goal:
Allow a well-trained programmer to be able to
implement.
Allow an expert to be able to analyze the running
time.

04/29/25 5
Data Structure
Deeply understand the basic structures used in
all software
 Understand the data structures and their trade-offs
 Rigorously analyze the algorithms that use them
(math!)
 Learn how to pick “the right thing for the job”
Practice design, analysis, and implementation
 The elegant interplay of “theory” and
“engineering” at the core of computer engineering

More programming experience (as a way to

learn)

04/29/25 6
Goals
Be able to make good design choices as a
developer, project manager, etc.
 Reason in terms of the general abstractions that
come up in all non-trivial software (and many
non-software) systems
Be able to justify and communicate your
design decisions

 Key abstractions used almost every day in just

about anything related to computing and
software
 It is a vocabulary you are likely to internalize
permanently

04/29/25 7
Data structures
(Often highly non-obvious) ways to
organize information to enable efficient
computation over that information
A data structure supports certain
operations, each with a:
 Meaning: what does the operation do/return
 Performance: how efficient is the operation
Examples:
 List with operations insert and delete
 Stack with operations push and pop

04/29/25 8
Trade-offs
A data structure strives to provide many useful,
efficient operations

But there are unavoidable trade-offs:

 Time vs. space
 One operation more efficient and another less
efficient
 Generality vs. simplicity vs. performance

We ask ourselves questions like:

 Does this support the operations I need efficiently?
 Will it be easy to use, implement, and debug?
 What assumptions am I making about how my
software will be used? (E.g., more lookups or more
inserts?)
04/29/25 9
Terminology
Abstract Data Type (ADT)
 Mathematical description of a “thing” with set of
operations
Algorithm
 A high level, language-independent description
of a step-by-step process
Data structure
 A specific organization of data and family of
algorithms for implementing an ADT
Implementation of a data structure
 A specific implementation in a specific language

04/29/25 10
An Example of an
Algorithm
Algorithm sorting(X, n)
Input array X of n integers
Output array X sorted in a non-decreasing order

for i  0 to n  1 do
for j  i+1 to n do
if (X[i]>X[j]) then
{ s=X[i];
X[i]=X[j];
X[j]=s;
}
return X

04/29/25 11
Analysis of Algorithms
Estimate the running time
Estimate the memory space
required.

Depends on the input size.

04/29/25 12
Running Time
Most algorithms transform best case
input objects into output average case
worst case
objects. 120

The running time of an 100

algorithm typically grows

Running Time
80
with the input size.
Average case time is 60

often difficult to 40

determine. 20

We focus on the worst 0

case running time. 1000 2000 3000 4000
I nput Size
 Easier to analyze
 Crucial to applications such

as games, finance and

robotics
04/29/25 13
Experimental Studies
Write a program 9000

implementing the 8000

algorithm 7000

Run the program with 6000

Time (ms)
inputs of varying size 5000
and composition 4000
Use a method like 3000
System.currentTimeMillis() to 2000
get an accurate
1000
measure of the actual
running time 0
0 50 100
Plot the results I nput Size

04/29/25 14
Limitations of Experiments
It is necessary to implement the
algorithm, which may be difficult
Results may not be indicative of the
running time on other inputs not
included in the experiment.
In order to compare two algorithms,
the same hardware and software
environments must be used

04/29/25 15
Theoretical Analysis
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
04/29/25 16
Pseudocode
High-level description Example: find
of an algorithm max element of
an array
More structured than Algorithm arrayMax(A, n)
English prose
Input array A of n integers
Less detailed than a
program Output maximum element of A
Preferred notation for currentMax  A[0]
describing algorithms for i  1 to n  1 do
Hides program design if A[i]  currentMax then
issues
currentMax  A[i]
return currentMax

04/29/25 17
Pseudocode Details
Control flow Expressions
 if … then … [else …]  Assignment
 while … do … (like  in Java)
 Equality testing
 repeat … until …
 for … do … (like  in Java)
 Indentation replaces n2 Superscripts and
braces other mathematical
formatting allowed
Method declaration
Algorithm method (arg [, arg…])
Input …
Output …

04/29/25 18
Primitive Operations
Basic computations
Examples:
performed by an algorithm
 Evaluating an
Identifiable in pseudocode expression
Largely independent from  Assigning a
the programming language value to a
variable
Exact definition not  Indexing into an
important array
Assumed to take a constant  Calling a method
amount of time in the RAM  Returning from a
model method

04/29/25 19
Counting Primitive
Operations
By inspecting the pseudocode, we can determine the
maximum number of primitive operations executed by
an algorithm, as a function of the input size

Algorithm arrayMax(A, n)
currentMax  A[0] 2
for (i =1; i<n; i++) 2n
(i=1 once, i<n n times, i++ (n-1) times)
if A[i]  currentMax then 2(n  1)
currentMax  A[i] 2(n  1)
return currentMax 1
Total 6n 

04/29/25 20
Estimating Running Time
Algorithm arrayMax executes 6n  1 primitive
operations in the worst case.
Define:
a = Time taken by the fastest primitive operation
b = Time taken by the slowest primitive operation
Let T(n) be worst-case time of arrayMax.
Then
a (6n  1)  T(n)  b(6n  1)
Hence, the running time T(n) is bounded by
two linear functions
04/29/25 21
Growth Rate of Running
Time
Changing the hardware/ software
environment
 Affects T(n) by a constant factor, but
 Does not alter the growth rate of T(n)
The linear growth rate of the
running time T(n) is an intrinsic
property of algorithm arrayMax

04/29/25 22
n logn n nlogn n2 n3 2n

4 2 4 8 16 64 16
8 3 8 24 64 512 256

16 4 16 64 256 4,096 65,536

32 5 32 160 1,024 32,768 4,294,967,296

64 6 64 384 4,094 262,144 1.84 * 1019

128 7 128 896 16,384 2,097,152 3.40 * 1038

256 8 256 2,048 65,536 16,777,216 1.15 * 1077

512 9 512 4,608 262,144 134,217,728 1.34 * 10154

1024 10 1,024 10,240 1,048,576 1,073,741,824 1.79 * 10308

The Growth Rate of the Six Popular functions

04/29/25 23
Big-Oh Notation
To simplify the running time
estimation,
for a function f(n), we ignore the
constants and lower order terms.

Example: 10n3+4n2-4n+5 is O(n3).

04/29/25 24
Big-Oh and Growth Rate
The big-Oh notation gives an upper bound on the
growth rate of a function
The statement “f(n) is O(g(n))” means that the
growth rate of f(n) is no more than the growth rate
of g(n)
We can use the big-Oh notation to rank functions
according to their growth rate

04/29/25 25
Big-Oh Rules

If f(n) is a polynomial of degree d, then f(n)

is O(nd), i.e.,
1. Drop lower-order terms
2. Drop constant factors
Use the smallest possible class of functions
 Say “2n is O(n)” instead of “2n is O(n2)”
Use the simplest expression of the class
 Say “3n  5 is O(n)” instead of “3n  5 is O(3n)”

04/29/25 26
Growth Rate of Running Time

Consider a program with time complexity O(n2).

For the input of size n, it takes 5 seconds.
If the input size is doubled (2n), then it takes 20 seconds.

Consider a program with time complexity O(n).

For the input of size n, it takes 5 seconds.
If the input size is doubled (2n), then it takes 10 seconds.

Consider a program with time complexity O(n3).

For the input of size n, it takes 5 seconds.
If the input size is doubled (2n), then it takes 40 seconds.

04/29/25 27
Asymptotic Algorithm
Analysis
The asymptotic analysis of an algorithm
determines the running time in big-Oh notation
To perform the asymptotic analysis
 We find the worst-case number of primitive
operations executed as a function of the input size
 We express this function with big-Oh notation
Example:
 We determine that algorithm arrayMax executes at
most 6n  1 primitive operations
 We say that algorithm arrayMax “runs in O(n) time”
Since constant factors and lower-order terms are
eventually dropped anyhow, we can disregard
them when counting primitive operations

04/29/25 28
Computing Prefix
Averages
We further illustrate
35
asymptotic analysis with X
two algorithms for prefix 30 A
averages
25
The i-th prefix average of
an array X is average of the 20
first (i  1) elements of X: 15
A[i] X[0]  X[1]  …  X[i])/(i+1)
10
Computing the array A of
prefix averages of another 5
array X has applications to 0
financial analysis 1 2 3 4 5 6 7

04/29/25 29
Prefix Averages (Quadratic)
The following algorithm computes prefix averages
in quadratic time by applying the definition

Algorithm prefixAverages1(X, n)
Input array X of n integers
Output array A of prefix averages of X #operations
A  new array of n integers n
for i  0 to n  1 do n
{ s  X[0] n
for j  1 to i do 1 2 … (n  1)
s  s  X[j] 1 2 … (n  1)
A[i]  s  (i  1) } n
return A 1

04/29/25 30
Arithmetic Progression
The running time of
prefixAverages1 is
O(1 2 …n)
The sum of the first n
integers is n(n 1) 2
 There is a simple
visual proof of this fact
Thus, algorithm
prefixAverages1 runs in
O(n2) time

04/29/25 31
Prefix Averages (Linear)
The following algorithm computes prefix
averages in linear time by keeping a running sum
Algorithm prefixAverages2(X, n)
Input array X of n integers
Output array A of prefix averages of X
#operations
A  new array of n integers n
s0 1
for i  0 to n  1 do n
{s  s  X[i] n
A[i]  s  (i  1) } n
return A 1
Algorithm prefixAverages2 runs in O(n) time
04/29/25 32
Exercise: Give a big-Oh
characterization

Algorithm Ex1(A, n)
Input an array X of n integers
Output the sum of the elements in A

s  A[0]
for i  0 to n  1 do
s  s  A[i]

return s

04/29/25 33
Exercise: Give a big-Oh
characterization

Algorithm Ex2(A, n)
Input an array X of n integers
Output the sum of the elements at even cells in A

s  A[0]
for i  2 to n  1 by increments of 2 do

s  s  A[i]
return s

04/29/25 34
Exercise: Give a big-Oh
characterization

Algorithm Ex1(A, n)
Input an array X of n integers
Output the sum of the prefix sums A
s0
for i  0 to n  1 do
s  s  A[0]
for j 1 to i do
s  s  A[j]
return s

04/29/25 35
General Rules
Rule 1—for loops.
The running time of a for loop is at
most the running time of the
statements inside the for loop
(including tests) times the number
of iterations.

04/29/25 36
Rules
Rule 2—Nested loops.
Analyze these inside out.
Example: for( i = 0;i<n;i++)
for( j = 0;j<n;j++)
k++;

04/29/25 37
Rules
Rule 3—Consecutive Statements.
These just add (which means that the maximum is the
one that counts).
Example:
for( i = 0;i<n;i++)
a[i]=0;
for( i = 0;i<n;i++)
for( j = 0;j<n;j++)
a[i]+=a[j]+i+j;
The running time is O(n)+O(n2)=O(n2)

04/29/25 38
Rules
Rule 4—if/else.
For the fragment
if( condition )
S1
else
S2
the running time of an if/else statement is never
more than the running time of the test plus the
larger of the running times of S1 and S2.

04/29/25 39
Problems
In a recent court case, a judge cited a city for
contempt and ordered a fine of $2 for the first
day. Each subsequent day, until the city
followed the judge’s order, the fine was
squared (that is, the fine progressed as
follows: $2, $4, $16, $256, $65, 536,...).
a. What would be the fine on day N?
b. How many days would it take the fine to reach D
dollars? (A Big-Oh answer will do.)

04/29/25 40
Problems
An algorithm takes 0.5 ms for input size
100. How long will it take for input size
500 if the running time is the following
(assume low-order terms are
negligible):
a. linear
b. O(NlogN)
c. quadratic
d. cubic
04/29/25 41