Lecture 4: Analysis of Algorithms II

Majid Khonji

201

1

www.avlab.io

Khalifa University

ROBO

Course Structure

Module 1: Algorithm Fundamentals

• Today:
• Analysis of algorithms part 2 (out of 4)
• The Big O notation

Module 2: Path Planning in Discrete Spaces

Module 3: Path Planning in Continuous Spaces

2

ku.ac.ae

Experimental Studies Approach

• One approach to test an Alg.:
• Write a program implementing the algorithm
• Run the program with inputs of varying size and composition, noting the time needed:
• Plot the results

​

3

import time

start_time = time.perf_counter()

# --- run the algorithm here ---

end_time = time.perf_counter()

elapsed = (end_time - start_time) * 1000

print("Elapsed time:", elapsed, "milliseconds")

ku.ac.ae

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

4

ku.ac.ae

Theoretical Analysis

• 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
• Uses a high-level description of the algorithm instead of an implementation

​

5

ku.ac.ae

Running Time

• Most algorithms transform input objects into output objects.
• The running time of an algorithm typically grows with the input size.
• Average case time is often difficult to determine.
• We focus on the worst-case running time.
• Easier to analyze
• Crucial to applications such as games, finance and robotics

6

ku.ac.ae

�Comparison of Two Algorithms

7

Insertion sort is

n² / 4

Merge sort is

2 n lg n

Sort a million items?

insertion sort takes

roughly 70 hours

while

merge sort takes

roughly 40 seconds

This is a slow machine, but if

100 x as fast then it’s 40 minutes

versus less than 0.5 seconds

ku.ac.ae

Seven Important Functions

• Seven functions that often appear in algorithm analysis:
• Constant ≈ 1
• Logarithmic ≈ log n
• Linear ≈ n
• N-Log-N ≈ n log n
• Quadratic ≈ n²
• Cubic ≈ n³
• Exponential ≈ 2ⁿ

8

ku.ac.ae

The Seven Functions

9

g(n) = n lg n

Slide by Matt Stallmann included with permission

Side by side

ku.ac.ae

�Why Growth Rate Matters

10

runtime

quadruples

when problem

size doubles

Growth Rate

• The growth rate of a function describes how fast it increases as input size grows
• Like the derivative
• Log-log chart is a compact way to show function of different scales
• On a log–log plot, the slope of the line equals the exponent of the function�n → slope ≈ 1, n² → slope ≈ 2, n³ → slope ≈ 3
• For large n, growth rate is determined only by the dominant term:
• constant factors and lower-order terms become negligible.

11

ku.ac.ae

Big-Oh Notation

• Given functions f(n) and g(n), we say that f(n) is O(g(n)) if there are positive constants�c and n₀ such that

f(n) ≤ cg(n) for n ≥ n₀

​

12

• Example: 2n + 10 is O(n)?

​

• 2n + 10 ≤ cn for n ≥ n₀
• (c − 2) n ≥ 10
• n ≥ 10/(c − 2) for c > 2
• Pick c = 3 and n₀ = 10

Note: n is input size so n₀ ≥ 1

c > 0

ku.ac.ae

More Big-Oh Examples

13

• 7n - 2

​

is O(n)

need c > 0 and n₀ ≥ 1 such that 7 n - 2 ≤ c n for n ≥ n₀

this is true for c = 8 and n₀ = 1

​

• 3 n³ + 20 n² + 5

​

is O(n³)

Notice for n or n ≥ 1, 20n² ≤ 20n³, 5 ≤ 5n³

f(n) = 3n³ + 20n² + 5 ≤ (3 + 20 + 5) n³ = 28n³.

You can pick c = 28 and n₀ = 1

• 3 log n + 5

is O(log n)

We need 3log n + 5 ≤ c log n ⟹ 5 ≤ (c−3) log n

For c > 3, 5/(c-3) ≤ log n. Choose c = 4 ⟹ 5 ≤ log n ⟹ 2⁵ ≤ n

Thus, c = 4, n₀ = 32

Log property�n = a^(logₐ n)

ku.ac.ae

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

14

ku.ac.ae

Big-Oh Rules

• If is f(n) a polynomial of degree d, then f(n) is O(n^d), 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(n²)”
• Use the simplest expression of the class
• Say “3n + 5 is O(n)” instead of “3n + 5 is O(3n)”

15

ku.ac.ae

Analysis Examples

16

Recall: Primitive Operations

• Examples of primitive operations:
• Evaluating an expression
• Assigning a value to a variable
• Indexing into an array
• Calling a method
• Returning from a method

17

ku.ac.ae

Counting Primitive Operations

Algorithm arrayMax(A, n)

currentMax ← A[0] 2

for i ← 1 to n − 1 do 2 + n

if A[i] > currentMax then 2(n − 1)

currentMax ← A[i] 2(n − 1)

{ increment counter i } 2(n − 1)

return currentMax 1

18

T(n) = 6 ( n - 1) + n + 5 = 7n + 4

= O(n) why?

7n + 4 ≤ cn�4/(7-c) ≤ n for c = 6 and n₀ = 4

ku.ac.ae

Example: Computing Prefix Averages

• We further illustrate asymptotic analysis with two algorithms for prefix averages
• The i-th prefix average of an array X is average of the first (i + 1) elements of X:

A[i] = (X[0] + X[1] + … + X[i])/(i+1)

• Computing the array A of prefix averages of another array X has applications to financial analysis

19

ku.ac.ae

Prefix Average Algorithm 1

The following algorithm computes prefix averages:

For simplicity, here we are not counting precisely all primitive operations. In the exams, I’ll give you a python code instead for precise count.

20

A ← new array of n integers

for i ← 0 to n – 1 do

s ← X[0]

for j ← 1 to i do

s ← s + X[j]

A[i] ← s / (i + 1)

return A

​

n

n

n

1 + 2 + … + (n – 1)

1 + 2 + … + (n – 1)

n

1

ku.ac.ae

Arithmetic Progression

What is the value of 1 + 2 + … + (n – 1)?

​

​

21

• Add them term by term:�2S = n+n+n+⋯+n (with n−1 terms)

= (n−1)n

S = (n-1)n/2 = (n² - n)/2

• Write the sum forward and backward:

S = 1 + 2 + 3 + ⋯ + (n−1)

S = (n−1) + (n−2) + (n−3) + ⋯ + 1

ku.ac.ae

Arithmetic Progression

Often written as

• Write the sum forward and backward:

S = 1 + 2 + 3 + ⋯ + n

S = n + (n-1) + (n-2) + ⋯ + 1

​

22

• Add them term by term:�2S = n + n + n + ⋯ + n (with n terms)

= (n+1)n

S = (n+1)n/2 = (n² + n)/2

Carl Friedrich Gauss

1777 - 1855

ku.ac.ae

Arithmetic Progression (Visual Proof)

• The yellow area:

1+2+⋯+n = n(n + 1) / 2

​

Example:

• Width = 6
• Height = 7
• Yellow Area: 7 x 6 / 2 = 21

​

Or, for n=6 the area 6 (6+1)/2

23

ku.ac.ae

Complexity of Prefix Average Algorithm 1

# Primitive Operations T(n) = 4n + 2 n(n-1)/2 + 1

24

A ← new array of n integers

for i ← 0 to n – 1 do

s ← X[0]

for j ← 1 to i do

s ← s + X[j]

A[i] ← s / (i + 1)

return A

​

n

n

n

1 + 2 + … + (n – 1)

1 + 2 + … + (n – 1)

n

1

= O(n²)

ku.ac.ae

Another Algorithm for Prefix Average

A ← new array of size n

total ← 0

for j ← 0 to n − 1 do

total ← total + X[j]

A[j] ← total / (j + 1)

return A

Whats the time complexity T(n)?

25

O(n)

ku.ac.ae

Math you need to Review

• Properties of powers:

a^(b+c) = a^ba ^c

a^bc = (a^b)^c

a^b /a^c = a^(b-c)

b = a^(logₐ b)

b^c = a^(c logₐ b)

• Properties of logarithms:

log_b(xy) = log_bx + log_by

log_b (x/y) = log_bx - log_by

Log_bx^a= alog_bx

log_ba = log_xa/log_xb

• Summations

​

• More summations later

26