CSE 373 Lecture 2: Mathematical Background Logs and exponents

✦ Today, we will review: ✦ We will be dealing mostly with binary numbers (base 2)
µ Logs and exponents
✦ Definition: logX B = A means X A = B
µ Series
µ Recursion ✦ Any base is equivalent to base 2 within a constant factor:
µ Big-Oh notation for analysis of algorithms
log 2 B
✦ Covered in Chapters 1 and 2 of the text log X B =
log 2 X

✦ Why?

R. Rao, CSE 373 Lecture 1 1 R. Rao, CSE 373 Lecture 1 2

Logs and exponents Properties of logs (of the mathematical kind)

✦ We will be dealing mostly with binary numbers (base 2) ✦ We will assume logs to base 2 unless specified otherwise
✦ Definition: logX B = A means X A = B ✦ log AB = log A + log B (note: log AB ≠ log A•log B)
✦ Any base is equivalent to base 2 within a constant factor: ✦ log A/B = log A – log B (note: log A/B ≠ log A / log B)
log 2 B ✦ (note: log AB ≠ (log A) B = log B A)
log X B = log AB = B log A
log 2 X
✦ log log X < log X < X for all X > 0
✦ Why? µ 2Y
log log X = Y means 2 = X
✦ Because: if R = log2 B, S = log2 X, and T = logX B, µ log X grows slower than X; called a “sub-linear” function

µ 2R = B, 2S = X, and XT = B ✦ log 1 = 0, log 2 = 1, log 1024 = 10

µ 2R = XT = 2ST i.e. R = ST and therefore, T = R/S.

R. Rao, CSE 373 Lecture 1 3 R. Rao, CSE 373 Lecture 1 4

Arithmetic Series A Sneak Preview of Algorithm Analysis

K+ N = ∑i = ?
N
✦ S (N ) = 1+ 2 + ✦ Consider the following program segment:
i =1 for (i = 1; i <= N; i++)
✦ The sum is: S(1) = 1, S(2) = 3, S(3) = 6, S(4) = 10, … for (j = 1; j <= i; j++)
printf(“Hello\n”);
✦ Is S(N) = N(N+1)/2 ?
µ Prove by induction (base case: N = 1, S(N) = 1(2)/2 = 1) ✦ How many times is “printf” executed?
µ Assume true for N = k: S(k) = k(k+1)/2 µ Or, How many Hello’s will you see?
µ Suppose N = k+1.
µ S(k+1) = 1 + 2 + …+ k + (k+1) = S(k) + (k+1)
= k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2. ✔

∑ i = N ( N2 + 1)
N
✦ Why is this formula useful?
i =1

R. Rao, CSE 373 Lecture 1 5 R. Rao, CSE 373 Lecture 1 6

A Sneak Preview of Algorithm Analysis Other Important Series (know them well!)

∑i
✦ The program segment being analyzed: ✦ Sum of squares: N
N ( N + 1)(2 N + 1) N 3
for (i = 1; i <= N; i++)
2
= ≈ for large N
i =1 6 3
for (j = 1; j <= i; j++)

∑i N k +1
N
printf(“Hello\n”);
✦ Sum of exponents:
k
≈ for large N and k ≠ -1
i =1 | k +1|
✦ Inner loop executes “printf” i times in the ith iteration

∑ 1i ≈ log N for large N

N
✦ There are N iterations in the outer loop (i goes from 1 to N) ✦ Harmonic series (k = -1): e
i =1
✦ Total number of times “printf” is executed = µ loge N (or ln N) is the natural log of N

∑ i = N ( N2 + 1)
N

∑ A = AA −−1 1
i =1 N N +1
i
✦ Congratulations - You’ve just analyzed your first program! ✦ Geometric series:
µ Running time of the program is proportional to N(N+1)/2 for all N.
i =0

R. Rao, CSE 373 Lecture 1 7 R. Rao, CSE 373 Lecture 1 8

Recursion Recursive Procedure for Fibonacci Numbers
✦ A function that calls itself is said to be recursive ✦ int fib(int i) {
µ We encountered a recursive procedure “sum” in the first lecture if (i < 0) return 0; //invalid input

✦ Recursion may be a natural way to program certain if (i == 0 || i == 1) return 1; //base cases

functions that involve repetitive calculations (as else return fib(i-1)+fib(i-2);

compared to iteration by “for” or “while” loops) }

✦ Classic example: Fibonacci numbers Fn ✦ Easy to write: looks like the definition of Fn
1, 1, 2, 3, 5, 8, 13, 21, 34, … ✦ But, can you spot a big problem?

µ First two are defined to be 1

µ Rest are sum of preceding two
µ Fn = Fn-1 + Fn-2 (n > 1)
Leonardo Pisano
R. Rao, CSE 373 Lecture 1 Fibonacci (1170-1250) 9 R. Rao, CSE 373 Lecture 1 10

Recursive Calls of Fibonacci Procedure Iterative Procedure for Fibonacci Numbers

✦ int fib_iter(int i) {

int fib0 = 1, fib1 = 1, fibj = 1;

if (i < 0) return 0; //invalid input

for (int j = 2; j <= i; j++) { //calculate all fib nos. up to i

fibj = fib0 + fib1;

fib0 = fib1;

fib1 = fibj;

return fibj;

✦ More variables and more bookkeeping but avoids

✦ Wastes precious time by re-computing fib(N-i) multiple repetitive calculations and saves time.
times, for i = 2, 3, 4, etc.! µ How much time is saved over the recursive procedure?
µ Answer in next class…
R. Rao, CSE 373 Lecture 1 11 R. Rao, CSE 373 Lecture 1 12
Recursion Summary Motivation for Big-Oh Notation
✦ Recursion may simplify programming, but beware of ✦ Suppose you are given two algorithms A and B for
generating large numbers of calls solving a problem
µ Function calls can be expensive in terms of time and space
µ There is a hidden space cost associated with the system’s stack ✦ Here is the running time TA(N) and TB(N) of A and B as a
function of input size N:
✦ Be sure to get the base case(s) correct!
TA
✦ Each step must get you closer to the base case

Run Time
✦ You may use induction to prove your program is correct Which algorithm
µ See example in previous lecture
would you choose?
TB

R. Rao, CSE 373 Lecture 1 13 R. Rao, CSE 373 Lecture 1 Input Size N 14

Motivation for Big-Oh Notation (cont.) Motivation for Big-Oh: Asymptotic Behavior

✦ For large N, the running time of A and B is: ✦ In general, what really matters is the “asymptotic”
performance as N → ∞, regardless of what happens for
small input sizes N.
Now which ✦ Performance for small input sizes may matter in practice,
Run Time

TA(N) = 50N if you are sure that small N will be common

algorithm would µ This is usually not the case for most applications
you choose?
✦ Given functions T1(N) and T2(N) that define the running
TB(N) = N2 times of two algorithms, we need a way to decide which
one is better (i.e. asymptotically smaller)
µ Big-Oh notation
Input Size N
R. Rao, CSE 373 Lecture 1 15 R. Rao, CSE 373 Lecture 1 16
Big-Oh Notation Big-Oh Notation
✦ T(N) = O(f(N)) if there are positive constants c and n0 ✦ T(N) = O(f(N)) if there are positive constants c and n0
such that T(N) ≤ cf(N) for N ≥ n0 . such that T(N) ≤ cf(N) for N ≥ n0 .
✦ We say that T(N) is “big-oh” of f(N) (or, order of f(N)) ✦ We say that T(N) is “big-oh” of f(N) or order of f(N)
✦ Example 1: Suppose T(N) = 50N. Then, T(N) = O(N) ✦ Example 1: Suppose T(N) = 50N. Then, T(N) = O(N)
µ Take c = 50 and n0 = 1 µ Take c = 50 and n0 = 1

✦ Example 2: Suppose T(N) = 50N+11. Then, T(N) = O(N) ✦ Example 2: Suppose T(N) = 50N+11. Then, T(N) = O(N)
µ T(N) ≤ 50N+11N = 61N for N ≥ 1. So, c = 61 and n0 = 1 works µ T(N) ≤ 50N+11N = 61N for N ≥ 1. So, c = 61 and n0 = 1 works

✦ Example 3: TA(N) = 50N, TB(N) = N2. ✦ Example 3: TA(N) = 50N, TB(N) = N2.
Show that TA(N) = O(TB(N)): what works for c and n0 ? TA(N) = O(TB(N)): choose c = 1 and n0 = 50

R. Rao, CSE 373 Lecture 1 17 R. Rao, CSE 373 Lecture 1 18

Common functions we will encounter…

Name Big-Oh
Constant O(1)
Log log O(log log N) Next Lecture: Using Big-Oh for Algorithm Analysis
Increasing cost

Logarithmic O(log N)
Log squared O((log N)2)
To do:

}
Linear O(N)
N log N O(N log N)
Polynomial time Finish reading Chapters 1 and 2
Quadratic O(N2)
Cubic O(N3)
Set up your account at MSCC lab
Exponential O(2N)

R. Rao, CSE 373 Lecture 1 19 R. Rao, CSE 373 Lecture 1 20