程序代写代做代考 algorithm AI math

math

Relevant Mathematics

Jeff Edmonds
York University

COSC 3101
Lecture skipped.
(Done when needed)
Thinking about Algorithms Abstractly

Logic Quantifiers
The Time Complexity of an Algorithm
Classifying Functions
Adding Made Easy
Recurrence Relations
In More Details

Some Math
Time Complexity

t(n) = Q(n2)
Logic Quantifiers
g “b Loves(b,g)
“b g Loves(b,g)
In Iterative Algs (GCD)
See logic slides

Some Math
Logs and Exps
2a × 2b = 2a+b
2log n = n
You are on your own.

Input Size
Time
Classifying Functions
f(i) = nQ(n)
See logic slides

Some Math
Recurrence Relations
T(n) = a T(n/b) + f(n)

Adding Made Easy
∑i=1 f(i).

In Iterative Algs
(Insertion Sort)

In Recursive Algs
(Multiplying)
In Recursive Algs
(Multiplying,
Towers of Hanoi,
Merge Sort)

The Time Complexity of an Algorithm
Specifies how the running time depends on the size of the input.

Purpose?

Purpose
To estimate how long a program will run.
To estimate the largest input that can reasonably be given to the program.
To compare the efficiency of different algorithms.
To help focus on the parts of code that are executed the largest number of times.
To choose an algorithm for an application.

Time Complexity Is a Function
Specifies how the running time depends on the size of the input.

A function mapping
“size” of input

“time” T(n) executed .

Definition of Time?

Definition of Time
# of seconds (machine dependent).
# lines of code executed.
# of times a specific operation is performed (e.g., addition).

Which?

Definition of Time
# of seconds (machine dependent).
# lines of code executed.
# of times a specific operation is performed (e.g., addition).

These are all reasonable definitions of time, because they are within a constant factor of each other.

Size of Input Instance?
83920

Size of Input Instance
Size of paper
# of bits
# of digits
Value

– n = 2 in2
– n = 17 bits
– n = 5 digits
– n = 83920
2’’
83920

1’’
Which are reasonable?

Size of Input Instance
Size of paper
# of bits
# of digits
Value
– n = 2 in2
– n = 17 bits
– n = 5 digits
– n = 83920
Intuitive
2’’
83920

1’’

Size of Input Instance
Size of paper
# of bits
# of digits
Value
– n = 2 in2
– n = 17 bits
– n = 5 digits
– n = 83920
Intuitive
Formal
2’’
83920

1’’

Size of Input Instance
Size of paper
# of bits
# of digits
Value
– n = 2 in2
– n = 17 bits
– n = 5 digits
– n = 83920
Intuitive
Formal
Reasonable
# of bits =
3.32 * # of digits
2’’
83920

1’’

Size of Input Instance
Size of paper
# of bits
# of digits
Value
– n = 2 in2
– n = 17 bits
– n = 5 digits
– n = 83920
Intuitive
Formal
Reasonable
Unreasonable
# of bits = log2(Value) Value = 2# of bits

2’’
83920

1’’

Two Example Algorithms
Sum N array entries:
A(1) + A(2) + A(3) + …
Factor value N:
Input N=5917 & Output N=97*61.
Algorithm N/2, N/3, N/4, …. ?

Time?

Time = N
Time = N
Is this reasonable?
No! One is considered fast and the other slow!

Two Example Algorithms
Sum N array entries:
A(1) + A(2) + A(3) + …
Factor value N:
Input N=5917 & Output N=97*61.
Algorithm N/2, N/3, N/4, …. ?

Standard input size?
Time = N
Time = N
N = hard drive
= 60G < 236 N = crypto key = 2100 19 Two Example Algorithms Sum N array entries: A(1) + A(2) + A(3) + … Factor value N: Input N=5917 & Output N=97*61. Algorithm N/2, N/3, N/4, …. ? Size of Input Instance? Time = N Time = N size n = N size n = log N 20 Two Example Algorithms Sum N array entries: A(1) + A(2) + A(3) + … Factor value N: Input N=5917 & Output N=97*61. Algorithm N/2, N/3, N/4, …. ? size n = N size n = log N Time as function of input size? Time for you to solve problem instance as a function of time for me to give you the problem instance. = n = 2n Time = N Time = N 21 Two Example Algorithms Sum N array entries: A(1) + A(2) + A(3) + … Factor value N: Input N=5917 & Output N=97*61. Algorithm N/2, N/3, N/4, …. ? Linear vs Exponential Time! size n = N size n = log N = n = 2n Time = N Time = N 22 Size of Input Instance? 14,23,25,30,31,52,62,79,88,98 23 Size of Input Instance # of elements = n = 10 elements 14,23,25,30,31,52,62,79,88,98 10 24 Size of Input Instance # of elements = n = 10 elements 14,23,25,30,31,52,62,79,88,98 10 Is this reasonable? 25 Size of Input Instance # of elements = n = 10 elements Reasonable 14,23,25,30,31,52,62,79,88,98 10 If each element has size c # of bits = c * # of elements 26 Size of Input Instance # of elements = n = 10 elements Reasonable 14,23,25,30,31,52,62,79,88,98 10 If each element is in [1..n] each element has size log n # of bits = n log n ≈ n ~ 27 Time Complexity Is a Function Specifies how the running time depends on the size of the input. A function mapping # of bits n needed to represent the input # of operations T(n) executed . 28 Which Input of size n? There are 2n inputs of size n. Which do we consider for the time T(n)? 29 Which Input of size n? Typical Input Average Case Worst Case 30 Which Input of size n? Typical Input But what is typical? Average Case For what distribution? Worst Case Time for all inputs is bound. Easiest to compute 31 What is the height of tallest person in the class? Bigger than this? Need to look at only one person Need to look at every person Smaller than this? 32 Time Complexity of Algorithm O(n2): Prove that for every input of size n, the algorithm takes no more than cn2 time. Ω(n2): Find one input of size n, for which the algorithm takes at least this much time. θ (n2): Do both. The time complexity of an algorithm is the largest time required on any input of size n. 33 Time Complexity of Problem O(n2): Provide an algorithm that solves the problem in no more than this time. Ω(n2): Prove that no algorithm can solve it faster. θ (n2): Do both. The time complexity of a problem is the time complexity of the fastest algorithm that solves the problem. 34 Classifying Functions T(n) 10 100 1,000 10,000 log n 3 6 9 13 amoeba n1/2 3 10 31 100 bird 10 100 1,000 10,000 human n log n 30 600 9,000 130,000 my father n2 100 10,000 106 108 elephant n3 1,000 106 109 1012 dinosaur 2n 1,024 1030 10300 103000 the universe Note: The universe contains approximately 1050 particles. n 35 Classifying Functions Functions Poly Logarithmic Polynomial Exponential Exp Double Exp Constant (log n)5 n5 25n 5 2 n5 25n 2 << << << << << (log n)θ(1) nθ(1) 2θ(n) θ(1) 2 nθ(1) 2θ(n) 2 36 Classifying Functions Linear Quadratic Cubic ? θ(n2) θ(n) θ(n3) Polynomial = nθ(1) θ(n4) Others θ(n3 log7(n)) log(n) not absorbed because not Mult-constant 37 Classifying Functions Functions Poly. Exp. 8·24n / n100 θ(24n / n100) 8·24n + n3 nθ(1) 2θ(n) θ(24n) 8·n2 θ(n2) θ(n3 log(n)) 7·n3log(n) We consider two (of many) levels in this hierarchy Individuals Ignore Mult-constant Ignore Power-constant 38 BigOh and Theta? 5n2 + 8n + 2log n = (n2) Drop low-order terms. Drop multiplicative constant. 5n2 log n + 8n + 2log n = (n2 log n) 39 Which Functions are Polynomials? nc n0.0001 n10000 5n2 + 8n + 2log n 5n2 log n 5n2.5 Drop low-order terms. Drop constant, log, (and poly) factors. Ignore power constant. Write nθ(1) 40 Which Functions are Exponential? 2n 20.0001 n 210000 n 8n 2n / n100 2n · n100 Drop low-order terms. Drop constant, log, and poly factors. Ignore power constant. Write 2θ(n) 41 Notations Theta f(n) = θ(g(n)) f(n) ≈ c g(n) BigOh f(n) = O(g(n)) f(n) ≤ c g(n) Omega f(n) = Ω(g(n)) f(n) ≥ c g(n) Little Oh f(n) = o(g(n)) f(n) << c g(n) Little Omega f(n) = ω(g(n)) f(n) >> c g(n)

Definition of Theta

f(n) = θ(g(n))

Definition of Theta
f(n) is sandwiched between c1g(n) and c2g(n)

f(n) = θ(g(n))

Definition of Theta
f(n) is sandwiched between c1g(n) and c2g(n)
for some sufficiently small c1 (= 0.0001)
for some sufficiently large c2 (= 1000)

f(n) = θ(g(n))

Definition of Theta
For all sufficiently large n

f(n) = θ(g(n))

Definition of Theta
For all sufficiently large n
For some definition of “sufficiently large”

f(n) = θ(g(n))

Definition of Theta

3n2 + 7n + 8 = θ(n2)

Order of Quantifiers

No! It cannot be a different c1 and c2
for each n.

f(n) = θ(g(n))

Gauss
∑i=1..n i = 1 + 2 + 3 + . . . + n
= ?
Arithmetic Sum

1 2 . . . . . . . . n
= number of white dots
1
+
2
+
3
+
. . .
+
n-1
+
n
=
S
Adding Made Easy

1
+
2
+
3
+
. . .
+
n-1
+
n
=
S
n
+
n-1
+
n-2
+
. . .
+
2
+
1
=
S

1 2 . . . . . . . . n
= number of yellow dots

n . . . . . . . 2 1
= number of white dots
Adding Made Easy

1
+
2
+
3
+
. . .
+
n-1
+
n
=
S
n
+
n-1
+
n-2
+
. . .
+
2
+
1
=
S
= number of white dots
= number of yellow dots
n+1 n+1 n+1 n+1 n+1
n
n
n
n
n
n
= n(n+1) dots in the grid

2S dots
S =
n (n+1)
2

Adding Made Easy

Gauss
∑i=1..n i = 1 + 2 + 3 + . . . + n
= Q(# of terms · last term)
Arithmetic Sum
True when ever terms increase slowly

∑i=0..n 2i = 1 + 2 + 4 + 8 +. . . + 2n
= ?
Geometric Sum

Geometric Sum

∑i=0..n 2i = 1 + 2 + 4 + 8 +. . . + 2n
= 2 · last term – 1
Geometric Sum

∑i=0..n ri = r0 + r1 + r2 +. . . + rn
= ?
Geometric Sum

S
Sr
r
r
r
.
.
.
r
r
S
Sr
1
r
S
r
1
r
1
2
3
n
n
1
n
1
n
1
=
1
r
r
r
.
.
.
2
3
r
n
+
+
+
+
+
=
+
+
+
+
+
–
=
–
=
–
–
+
+
+
Geometric Sum

∑i=0..n ri
r
1
r
1
n
1
=
–
–
+
Geometric Sum

When r>1?

∑i=0..n ri
r
1
r
1
n
1
=
–
–
+
Geometric Sum

= θ(rn)
Biggest Term

When r>1

∑i=0..n ri = r0 + r1 + r2 +. . . + rn
= Q(biggest term)

Geometric Increasing
True when ever terms increase quickly

∑i=0..n ri
=
Geometric Sum

When r<1? 1 r 1 r n 1 + - - 63 ∑i=0..n ri = Geometric Sum 1 r 1 r n 1 + - - = θ(1) When r<1 Biggest Term 64 ∑i=0..n ri = r0 + r1 + r2 +. . . + rn = Q(1) Bounded Tail True when ever terms decrease quickly 65 ∑i=1..n 1/i = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + …+ 1/n = ? Harmonic Sum 66 f(i) = 1 ∑i=1..n f(i) = n n Sum of Shrinking Function 67 f(i) = ? ∑i=1..n f(i) = n1/2 n Sum of Shrinking Function 68 f(i) = 1/2i ∑i=1..n f(i) = 2 ¥ Sum of Shrinking Function 69 f(i) = 1/i ∑i=1..n f(i) = ? n Sum of Shrinking Function 70 Harmonic Sum 71 ∑i=1..n 1/i = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + …+ 1/n = Q(log(n)) Harmonic Sum 72 Approximating Sum by Integrating The area under the curve approximates the sum ∑i=1..n f(i) ≈ ∫x=1..n f(x) dx 73 Adding Made Easy (For +, -, ×,  , exp, log functions f(n)) 74 Adding Made Easy 75 Geometric Like: If f(n) ³ 2Ω(n), then ∑i=1..n f(i) = θ(f(n)). Arithmetic Like: If f(n) = nθ(1)-1, then ∑i=1..n f(i) = θ(n · f(n)). Harmonic: If f(n) = 1/n , then ∑i=1..n f(i) = logen + θ(1). Bounded Tail: If f(n) £ n-1-Ω(1), then ∑i=1..n f(i) = θ(1). (For +, -, ×,  , exp, log functions f(n)) This may seem confusing, but it is really not. It should help you compute most sums easily. Adding Made Easy 76 Recurrence Relations T(1) = 1 T(n) = a T(n/b) + f(n) 77 Recurrence Relations » Time of Recursive Program With all this recursing and looping, how do we determine the running time of this recursive program? procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) T(1) = 1 T(n) = a T(n/b) + f(n) Recurrence relations. 78 Recurrence Relations » Time of Recursive Program Let n be the “size” of our input. procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) T(1) = 1 T(n) = a T(n/b) + f(n) 79 Recurrence Relations » Time of Recursive Program Let T(n) be the # of “Hi”s printed by me procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) T(1) = 1 T(n) = a T(n/b) + f(n) 80 Recurrence Relations » Time of Recursive Program Let T(n) be the # of “Hi”s printed by me And by all of my friends. procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) T(1) = 1 T(n) = a T(n/b) + f(n) 81 If my input is sufficiently small (according to my measure of size) then I print (1) “Hi”s. Recurrence Relations » Time of Recursive Program procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) T(1) = 1 T(n) = a T(n/b) + f(n) 82 I personally output f(n) “Hi”s, i.e. top level stack frame. Recurrence Relations » Time of Recursive Program procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) T(1) = 1 T(n) = a T(n/b) + f(n) 83 I have a friends i.e. recurse a times. Recurrence Relations » Time of Recursive Program procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) T(1) = 1 T(n) = a T(n/b) + f(n) 84 Let b be the factor by which I shrink the input before giving it to a friend. i.e. if my input has size n then my friends are of size n/b. Recurrence Relations » Time of Recursive Program procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) T(1) = 1 T(n) = a T(n/b) + f(n) 85 By definition of T, the number of “Hi”s printed by one of my friends and all of his friends is T(n/b). Recurrence Relations » Time of Recursive Program procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) T(1) = 1 T(n) = a T(n/b) + f(n) 86 Hence, the total number printed by me and my a friends is T(n) = a T(n/b) + f(n) Recurrence Relations » Time of Recursive Program procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) T(1) = 1 T(n) = a T(n/b) + f(n) 87 Evaluating: T(n) = aT(n/b)+f(n) Level Instance size Work in stack frame # stack frames Work in Level 0 n f(n) 1 1 · f(n) 1 n/b f(n/b) a a · f(n/b) 2 n/b2 f(n/b2) a2 a2 · f(n/b2) i n/bi f(n/bi) ai ai · f(n/bi) h = log n/log b n/bh T(1) n log a/log b n · T(1) log a/log b Dominated by Top Level or Base Cases 88 Evaluating: T(n) = aT(n/b)+f(n) 89 Merge Sort Sort Time: T(n) = = Q(n log(n)) 2T(n/2) + Q(n) Total work at any level = Q(n) # levels = Q(log(n)) 90 Evaluating: T(n) = aT(n/b)+f(n) Level Instance size Work in stack frame # stack frames Work in Level 0 n f(n) 1 1 · f(n) 1 n/b f(n/b) a a · f(n/b) 2 n/b2 f(n/b2) a2 a2 · f(n/b2) i n/bi f(n/bi) ai ai · f(n/bi) h = log n/log b n/bh T(1) n log a/log b n · T(1) log a/log b Total Work T(n) = ∑i=0..h ai×f(n/bi) 2T(n/2) + Q(n) 2i·Q(n/2i) = Q(n) = Q(n) · log(n) All levels basically the same. 91 Evaluating: T(n) = aT(n/b)+f(n) 92 Logs log 27 log 9 = 93 Logs log? 27 log? 9 = Which base? 94 Logs log2 27 log2 9 = It does not matter. log2 c log2 c · logc 27 · logc 9 = logc 27 logc 9 Which is easiest? 95 Logs log3 27 log3 9 = log3 33 log3 32 = 3 2 Please no calculators in exams. And I wont ask log 25 log 9 96 Evaluating: T(n) = 4T(n/2)+ n3/log5n 97 Time for top level?: Evaluating: T(n) = 4T(n/2)+ n3/log5n 98 Time for top level: f(n) = n3/log5n Time for base cases?: Evaluating: T(n) = 4T(n/2)+ n3/log5n 99 Time for top level: f(n) = n3 /log5n Time for base cases: Evaluating: T(n) = 4T(n/2)+ n3/log5n θ(n ) = log a/log b θ(n ) log ?/log ? 100 Time for top level: f(n) = n3 /log5n Time for base cases: Evaluating: T(n) = 4T(n/2)+ n3/log5n θ(n ) = log a/log b θ(n ) = ? log 4/log 2 101 Time for top level: f(n) = n3/log5n Time for base cases: Dominated?: c = ? Evaluating: T(n) = 4T(n/2)+ n3/log5n θ(n ) = log a/log b θ(n ) = θ(n2) log 4/log 2 log a/log b = ? 102 Time for top level: f(n) = n3/log5n Time for base cases: Dominated?: c = 3 > 2 = log a/log b

Evaluating: T(n) = 4T(n/2)+ n3/log5n
θ(n ) =
log a/log b
θ(n ) = θ(n2)
log 4/log 2
Hence, T(n) = ?

103

Time for top level: f(n) = n3/log5n
Time for base cases:
Dominated?: c = 3 > 2 = log a/log b

Evaluating: T(n) = 4T(n/2)+ n3/log5n
θ(n ) =
log a/log b
θ(n ) = θ(n2)
log 4/log 2
Hence, T(n) = θ(top) = θ(f(n)) = θ(n3/log5n).

104

Time for top level: f(n) = 2n
Time for base cases:
Dominated?: c = ? > 2 = log a/log b

Evaluating: T(n) = 4T(n/2)+ 2n
θ(n ) =
log a/log b
θ(n ) = θ(n2)
log 4/log 2
Hence, T(n) = θ(top) = θ(f(n)) = θ(2n).

bigger
>big
The time is even more dominated
by the top level of recursion

105

Time for top level: f(n) = n log5n
Time for base cases:
Dominated?: c = ? 2 = log a/log b

Evaluating: T(n) = 4T(n/2)+ n log5n
θ(n ) =
log a/log b
θ(n ) = θ(n2)
log 4/log 2

Hence, T(n) = ?
1< = θ(base cases) = θ(n ) = θ(n2). log a/log b 106 Time for top level: f(n) = log5n Time for base cases: Dominated?: c = ? 2 = log a/log b Evaluating: T(n) = 4T(n/2)+ log5n θ(n ) = log a/log b θ(n ) = θ(n2) log 4/log 2 Hence, T(n) = ? 0< = θ(base cases) = θ(n ) = θ(n2). log a/log b 107 Time for top level: f(n) = n2 Time for base cases: Dominated?: c = ? 2 = log a/log b Evaluating: T(n) = 4T(n/2)+ n2 θ(n ) = log a/log b θ(n ) = θ(n2) log 4/log 2 Hence, T(n) = ? 2= = θ(f(n) log(n) ) = θ(n2 log(n)). 108 Time for top level: f(n) = n2 log5n Time for base cases: Dominated?: c = 2 = 2 = log a/log b Evaluating: T(n) = 4T(n/2)+ n2 log5n θ(n ) = log a/log b θ(n ) = θ(n2) log 4/log 2 d = ? 5 ? Hence, T(n) = ? > -1
= θ(f(n) log(n) ) = θ(n2 log6(n)).

109

Evaluating: T(n) = aT(n/b)+f(n)

110

Evaluating: T(n) = aT(n-b)+f(n)
h = ?
n-hb

n-ib

n-2b
n-b
T(0)

f(n-ib)

f(n-2b)
f(n-b)
f(n)
n
Work in Level
# stack frames
Work
in stack
frame
Instance
size

a2
a
1
n/b
a · T(0)

ai · f(n-ib)

a2 · f(n-2b)
a · f(n-b)
1 · f(n)
n/b
|base case| = 0 = n-hb
h = n/b
h = n/b

Level

Likely dominated by base cases

Exponential

111

Evaluating: T(n) = 1T(n-b)+f(n)
h = ?
Work in Level
# stack frames
Work
in stack
frame
Instance
size

1
1
1

f(0)

f(n-ib)

f(n-2b)
f(n-b)
f(n)

n-b
n
n-hb

n-ib

n-2b
T(0)

f(n-ib)

f(n-2b)
f(n-b)
f(n)
h = n/b

Level

Total Work T(n) = ∑i=0..h f(b·i)
= θ(f(n)) or θ(n·f(n))

112

Evaluating: T(n) = aT(n/b)+f(n)

113

Relevant Mathematics
In more detail.
Jeff Edmonds
York University

COSC 3101
Lecture skipped
Thinking about Algorithms Abstractly

Classifying Functions
The Time Complexity of an Algorithm
Adding Made Easy
Recurrence Relations

Assumed Knowledge
Read the section on
Existential and Universal Quantifiers,

Logarithms and Exponentials

g “b Loves(b,g)
“b g Loves(b,g)

Start With Some Math

Input Size
Time
Classifying Functions
f(i) = nQ(n)
Recurrence Relations
T(n) = a T(n/b) + f(n)

Adding Made Easy
∑i=1 f(i).

Time Complexity

t(n) = Q(n2)

Classifying Functions
Giving an idea of how fast a function grows without going into too much detail.

Which are more alike?

Mammals

Which are more alike?

Dogs

Classifying Animals
Vertebrates
Birds
Mammals
Reptiles
Fish
Dogs
Giraffe

We consider two (of many)
levels in this hierarchy
Class
Genus
Individuals

Classifying Functions

T(n)

100

1,000

10,000

log n

amoeba

n1/2

100

bird

100

1,000

10,000

human

n log n

600

9,000

130,000

my father

100

10,000

106

108

elephant

1,000

106

109

1012

dinosaur

1,024

1030

10300

103000

the universe

Note: The universe contains approximately 1050 particles.

Which are more alike?
n1000
n2
2n

Which are more alike?

Polynomials
n1000
n2
2n

Which are more alike?
1000n2
3n2
2n3

Polynomials

Which are more alike?

Quadratic
1000n2
3n2
2n3
Polynomials

Classifying Functions?
Functions

Classifying Functions
Functions
Poly Logarithmic
Polynomial
Exponential
Exp
Double Exp
Constant
(log n)5
n5
25n
5
2
n5
25n
2
Others
2n log(n)

Classifying Functions?
Polynomial

Classifying Functions
Polynomial
Linear
Quadratic
Cubic
?
5n2
5n
5n3
5n4
Others
5n3 log7(n)

Classifying Functions
Functions
Poly.
Exp.
8·24n / n100

θ(24n / n100)
8·24n + n3
nθ(1)
2θ(n)
θ(24n)

8·n2

θ(n2)
θ(n3 log(n))

7·n2 + n
We consider two (of many)
levels in this hierarchy
Ignore
Power-constant
Ignore
Mult-constant
Individuals

Logarithmic
log10n = # digits to write n
log2n = # bits to write n
= 3.32 log10n
log(n1000) = 1000 log(n)
Differ only by a multiplicative constant.

Poly Logarithmic
(log n)5 = log5 n

Logarithmic << Polynomial For sufficiently large n log1000 n << n0.001 Linear << Quadratic For sufficiently large n 10000 n << 0.0001 n2 Polynomial << Exponential For sufficiently large n n1000 << 20.001 n Classifying Functions Functions Poly Logarithmic Polynomial Exponential Exp Double Exp Constant (log n)5 n5 25n 5 2 n5 25n 2 << << << << << Which Functions are Constant? 5 1,000,000,000,000 0.0000000000001 -5 0 8 + sin(n) Yes Yes Yes No Yes Yes Which Functions are “Constant”? 5 1,000,000,000,000 0.0000000000001 -5 0 8 + sin(n) Yes Yes Yes No No Yes Lie in between 7 9 The running time of the algorithm is a “Constant” It does not depend significantly on the size of the input. Write θ(1). Which Functions are Quadratic? n2 … ? Which Functions are Quadratic? n2 0.001 n2 1000 n2 Some constant times n2. Which Functions are Quadratic? n2 0.001 n2 1000 n2 5n2 + 3000n + 2log n Which Functions are Quadratic? n2 0.001 n2 1000 n2 5n2 + 3000n + 2log n Lie in between Which Functions are Quadratic? n2 0.001 n2 1000 n2 5n2 + 3000n + 2log n Ignore multiplicative constant. Low-order terms absorbed into constant. Ignore "small" values of n. Write θ(n2). Classifying Functions Functions Poly. Exp. 8·24n / n100 θ(24n / n100) 8·24n + n3 nθ(1) 2θ(n) θ(24n) 8·n2 θ(n2) θ(n3 log(n)) 7·n2 + n We consider two (of many) levels in this hierarchy Ignore Mult-constant Individuals Ignore Power-constant Classifying Functions Functions Poly. Exp. 8·24n / n100 θ(24n / n100) 8·24n + n3 nθ(1) 2θ(n) θ(24n) 8·n2 θ(n2) θ(n3 log(n)) 7·n2 + n We consider two (of many) levels in this hierarchy Ignore Mult-constant Individuals Ignore Power-constant log(n) not absorbed because not Mult-constant Which Functions are Polynomial? n5 … ? Which Functions are Polynomial? nc n0.0001 n10000 n to some constant power. Which Functions are Polynomial? nc n0.0001 n10000 5n2 + 8n + 2log n 5n2 log n 5n2.5 Which Functions are Polynomial? nc n0.0001 n10000 5n2 + 8n + 2log n 5n2 log n 5n2.5 Lie in between Which Functions are Polynomials? nc n0.0001 n10000 5n2 + 8n + 2log n 5n2 log n 5n2.5 Ignore power constant. Low-order terms and log factors absorbed into constant. Write nθ(1) Classifying Functions Functions Poly. Exp. 8·24n / n100 θ(24n / n100) 8·24n + n3 nθ(1) 2θ(n) θ(24n) 8·n2 θ(n2) θ(n3 log(n)) 7·n2 + n We consider two (of many) levels in this hierarchy Ignore Mult-constant Individuals Ignore Power-constant If f(n) = c ban nd loge (n) c Î ? a Î ? b Î ? d Î ? e Î ? > 0
= 0
or b = 1
> 0
(-¥,¥)

Which Functions are Polynomials?
then f(n) Î nθ(1)

Which Functions are Exponential?
2n
… ?

Which Functions are Exponential?
2n
20.0001 n
210000 n
2 raised to the power of
n times some constant power

Which Functions are Exponential?
2n
20.0001 n
210000 n
8n
2n / n100
2n · n100

too small?
too big?

Which Functions are Exponential?
2n
20.0001 n
210000 n
8n
2n / n100
2n · n100
= 23n
> 20.5n
< 22n Lie in between Which Functions are Exponential? 2n 20.0001 n 210000 n 8n 2n / n100 2n · n100 = 23n > 20.5n
< 22n 20.5n > n100
2n = 20.5n · 20.5n > n100 · 20.5n
2n / n100 > n0.5n

Which Functions are Exponential?
Ignore power constant.
Low-order terms, change in base,
and polynomial factors
absorbed into constant.
Write 2θ(n)

2n
20.0001 n
210000 n
8n
2n / n100
2n · n100

Classifying Functions
Functions
Poly.
Exp.
8·24n / n100

θ(24n / n100)
8·24n + n3
nθ(1)
2θ(n)
θ(24n)

8·n2

θ(n2)
θ(n3 log(n))

7·n2 + n
We consider two (of many)
levels in this hierarchy
Ignore
Mult-constant
Individuals

Ignore
Power-constant

If f(n) = c ban nd loge (n)
c Î ?
a Î ?
b Î ?
d Î ?
e Î ?

then f(n) Î 2θ(n)
> 0
> 0
> 1
(-¥,¥)
(-¥,¥)

Which Functions are Exponential?

Classifying Functions
Functions
Poly Logarithmic
Polynomial
Exponential
Exp
Double Exp
Constant
(log n)θ(1)
nθ(1)
2θ(n)
θ(1)
2
nθ(1)
2θ(n)
2
Ignore
Power-constant

Classifying Functions
Linear
Quadratic
Cubic
?
θ(n2)
θ(n)
θ(n3)
Polynomial
= nθ(1)
θ(n4)
Others
θ(n3 log7(n))
Ignore
Mult-constant

Exponential
2n vs 8n
Should these be classified together?
8n = 4n · 2n >> 1,000,000 · 2n
8n = 2log(8) · n = 23n
No:
8n ¹ Q(2n)
Yes:
8n = 2Q(n)
Ignore Power-constant
Ignore Mult-constant

Classifying Functions
Rank constants in significance.

f(n) = 8·24n / n100 + 5·n3
Tell me the most significant thing about your function

Classifying Functions
f(n) = 8·24n / n100 + 5·n3
f(n) = 9·24n / n100 + 5·n3
vs
additive:
multiplicative:
9/8
24n / n100

Rank constants in significance.

Classifying Functions
f(n) = 8·24n / n100 + 5·n3
f(n) = 8·24n / n100 + 6·n3
vs
≈ 1
n3

Rank constants in significance.
additive:
multiplicative:

Classifying Functions
f(n) = 8·24n / n100 + 5·n3
f(n) = 8·24n / n100 + 5·n4
vs
≈ 1
≈ 5· n4

Rank constants in significance.
additive:
multiplicative:

Classifying Functions
f(n) = 8·24n / n100 + 5·n3
f(n) = 8·25n / n100 + 5·n3
vs
multiplicative:
2n

Rank constants in significance.

Classifying Functions
f(n) = 8·24n / n100 + 5·n3
f(n) = 8·24n / n101 + 5·n3
vs
multiplicative:
n

Rank constants in significance.

Classifying Functions
f(n) = 8·24n / n100 + 5·n3
Rank constants in significance.
1

1’

Classifying Functions
f(n) = 8·24n / n100 + 5·n3
Rank constants in significance.
Significant Less significant

Irrelevant

Classifying Functions

f(n) = 8·24n / n100 + 5·n3
Tell me the most significant thing about your function

2θ(n)
23n < < 24n f(n) because Classifying Functions f(n) = 8·24n / n100 + 5·n3 Tell me the most significant thing about your function 2θ(n) 24n/nθ(1) θ(24n/n100) 8·24n / n100 + θ(n3) 8·24n / n100 + nθ(1) 8·24n / n100 + 5·n3 Classifying Functions Functions Poly. Exp. 8·24n / n100 + n3, θ(24n / n100) 8·24n + n3 nθ(1) 2θ(n) θ(24n) Ignore Mult-constant Individuals Ignore Power-constant Notations Theta f(n) = θ(g(n)) f(n) ≈ c g(n) BigOh f(n) = O(g(n)) f(n) ≤ c g(n) Omega f(n) = Ω(g(n)) f(n) ≥ c g(n) Little Oh f(n) = o(g(n)) f(n) << c g(n) Little Omega f(n) = ω(g(n)) f(n) >> c g(n)

Definition of Theta

f(n) = θ(g(n))

Definition of Theta
f(n) is sandwiched between c1g(n) and c2g(n)

f(n) = θ(g(n))

Definition of Theta
f(n) is sandwiched between c1g(n) and c2g(n)
for some sufficiently small c1 (= 0.0001)
for some sufficiently large c2 (= 1000)

f(n) = θ(g(n))

Definition of Theta
For all sufficiently large n

f(n) = θ(g(n))

Definition of Theta
For all sufficiently large n
For some definition of “sufficiently large”

f(n) = θ(g(n))

Definition of Theta

3n2 + 7n + 8 = θ(n2)

Definition of Theta

3n2 + 7n + 8 = θ(n2)
c1·n2 £ 3n2 + 7n + 8 £ c2·n2
?
?

Definition of Theta

3n2 + 7n + 8 = θ(n2)
3·n2 £ 3n2 + 7n + 8 £ 4·n2
3
4

Definition of Theta

3n2 + 7n + 8 = θ(n2)
3·12 £ 3·12 + 7·1 + 8 £ 4·12
1

False

Definition of Theta

3n2 + 7n + 8 = θ(n2)
3·72 £ 3·72 + 7·7 + 8 £ 4·72
7

False

Definition of Theta

3n2 + 7n + 8 = θ(n2)
3·82 £ 3·82 + 7·8 + 8 £ 4·82
8

True

Definition of Theta

3n2 + 7n + 8 = θ(n2)
3·92 £ 3·92 + 7·9 + 8 £ 4·92
9

True

Definition of Theta

3n2 + 7n + 8 = θ(n2)
3·102 £ 3·102 + 7·10 + 8 £ 4·102
10

True

Definition of Theta

3n2 + 7n + 8 = θ(n2)
3·n2 £ 3n2 + 7n + 8 £ 4·n2

Definition of Theta

3n2 + 7n + 8 = θ(n2)
3·n2 £ 3n2 + 7n + 8 £ 4·n2

n ³ 8
8

Definition of Theta

3n2 + 7n + 8 = θ(n2)
3·n2 £ 3n2 + 7n + 8 £ 4·n2

True
n ³ 8

Definition of Theta

3n2 + 7n + 8 = θ(n2)
3·n2 £ 3n2 + 7n + 8 £ 4·n2

7n + 8 £ 1·n2
7 + 8/n £ 1·n
n ³ 8
True

Definition of Theta

3n2 + 7n + 8 = θ(n2)
3·n2 £ 3n2 + 7n + 8 £ 4·n2
3
4
8

n ³ 8
True

Definition of Theta

n2 = θ(n3)

Definition of Theta

n2 = θ(n3)
c1 · n3 £ n2 £ c2 · n3
?
?

Definition of Theta

n2 = θ(n3)
0 · n3 £ n2 £ c2 · n3
0

True, but ?

Definition of Theta

n2 = θ(n3)

Constants c1 and c2 must be positive!

False

Definition of Theta

3n2 + 7n + 8 = θ(n)

Definition of Theta

3n2 + 7n + 8 = θ(n)
c1·n £ 3n2 + 7n + 8 £ c2·n
?
?

Definition of Theta

3n2 + 7n + 8 = θ(n)
3·n £ 3n2 + 7n + 8 £ 100·n
3
100

Definition of Theta

3n2 + 7n + 8 = θ(n)
3·n £ 3n2 + 7n + 8 £ 100·n
?

Definition of Theta

3n2 + 7n + 8 = θ(n)
3·100 £ 3·1002 + 7·100 + 8 £ 100·100
100

False

Definition of Theta

3n2 + 7n + 8 = θ(n)
3·n £ 3n2 + 7n + 8 £ 10,000·n
3
10,000

Definition of Theta

3n2 + 7n + 8 = θ(n)
3·10,000 £ 3·10,000 2 + 7·10,000 + 8 £ 10,000·10,000
10,000

False

Definition of Theta

3n2 + 7n + 8 = θ(n)

What is the
reverse statement?

Understand Quantifiers!!!
Sam Mary
Bob Beth
John Marilyn Monroe
Fred Ann

Sam Mary
Bob Beth
John Marilyn Monroe
Fred Ann

$ b, ØLoves(b, MM)
” b, Loves(b, MM)
Ø[$ b, ØLoves(b, MM)]
Ø[” b, Loves(b, MM)]

Definition of Theta

3n2 + 7n + 8 = θ(n)

The reverse statement

Definition of Theta

3n2 + 7n + 8 = θ(n)

3n2 + 7n + 8 > 100·n
3

100
?

Definition of Theta

3n2 + 7n + 8 = θ(n)

3·1002 + 7·100 + 8 > 100·100
3

100

True
100

Definition of Theta

3n2 + 7n + 8 = θ(n)

3n2 + 7n + 8 > 10,000·n
3

10,000
?

Definition of Theta

3n2 + 7n + 8 = θ(n)

3·10,0002 + 7·10,000 + 8 > 10,000·10,000

10,000

True
10,000

Definition of Theta

3n2 + 7n + 8 = θ(n)

3n2 + 7n + 8 > c2·n
c1

c2
?

Definition of Theta

3n2 + 7n + 8 = θ(n)

3·c22 + 7 · c2 + 8 > c2·c2
c1

True
c2

Definition of Theta

3n2 + 7n + 8 = θ(n)

3n2 + 7n + 8 > c2·n
c1

c2
?

Definition of Theta

3n2 + 7n + 8 = θ(n)

3·c22 + 7 · c2 + 8 > c2·c2
c1

max(c2,n0 )

True
c2

n0
True

Definition of Theta

3n2 + 7n + 8 = g(n)θ(1)

$ c1, c2, n0, ” n ³ n0 g(n)c1 £ f(n) £ g(n)c2
3n2 + 7n + 8 = nθ(1)

Definition of Theta

3n2 + 7n + 8 = nθ(1)
nc1 £ 3n2 + 7n + 8 £ nc2
$ c1, c2, n0, ” n ³ n0 g(n)c1 £ f(n) £ g(n)c2
?
?

Definition of Theta

3n2 + 7n + 8 = nθ(1)
n2 £ 3n2 + 7n + 8 £ n3
$ c1, c2, n0, ” n ³ n0 g(n)c1 £ f(n) £ g(n)c2
2
3

Definition of Theta

3n2 + 7n + 8 = nθ(1)
n2 £ 3n2 + 7n + 8 £ n3
$ c1, c2, n0, ” n ³ n0 g(n)c1 £ f(n) £ g(n)c2
2
3

n ³ ?

Definition of Theta

3n2 + 7n + 8 = nθ(1)
n2 £ 3n2 + 7n + 8 £ n3

$ c1, c2, n0, ” n ³ n0 g(n)c1 £ f(n) £ g(n)c2
2
3

n ³ 5

Definition of Theta

3n2 + 7n + 8 = nθ(1)
n2 £ 3n2 + 7n + 8 £ n3
True
True
$ c1, c2, n0, ” n ³ n0 g(n)c1 £ f(n) £ g(n)c2
2
3

n ³ 5

Order of Quantifiers

f(n) = θ(g(n))

Understand Quantifiers!!!
One girl
Could be a separate girl for each boy.
Sam Mary
Bob Beth
John Marilyn Monroe
Fred Ann

Sam Mary
Bob Beth
John Marilyn Monroe
Fred Ann

Order of Quantifiers

No! It cannot be a different c1 and c2
for each n.

f(n) = θ(g(n))

Other Notations
Theta f(n) = θ(g(n)) f(n) ≈ c g(n)
BigOh f(n) = O(g(n)) f(n) ≤ c g(n)
Omega f(n) = Ω(g(n)) f(n) ≥ c g(n)
Little Oh f(n) = o(g(n)) f(n) << c g(n) Little Omega f(n) = ω(g(n)) f(n) >> c g(n)

BigOh Notation
n2 = O(n3)
n3 = O(n2)

BigOh Notation
O(n2) = O(n3)
O(n3) = O(n2)

Odd Notation
f(n) = O(g(n)) Standard

f(n) ≤ O(g(n)) Stresses one function dominating another.

f(n)ÎO(g(n)) Stress function is member of class.

Adding
The Classic Techniques
Evaluating ∑i=1 f(i).
n

Gauss
∑i=1..n i = 1 + 2 + 3 + . . . + n
= ?
Arithmetic Sum

1 + 2 + 3 + . . . + n-1 + n = S
n + n-1 + n-2 + . . . + 2 + 1 = S

(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2S
n (n+1) = 2S

1 + 2 + 3 + . . . + n-1 + n = S
n + n-1 + n-2 + . . . + 2 + 1 = S

(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2S
n (n+1) = 2S

1 + 2 + 3 + . . . + n-1 + n = S
n + n-1 + n-2 + . . . + 2 + 1 = S

(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2S
n (n+1) = 2S

1 + 2 + 3 + . . . + n-1 + n = S
n + n-1 + n-2 + . . . + 2 + 1 = S

(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2S
n (n+1) = 2S

Let’s restate this argument using a geometric representation

Algebraic argument

1 2 . . . . . . . . n
= number of white dots.

1 2 . . . . . . . . n
= number of white dots
= number of yellow dots

n . . . . . . . 2 1

n+1 n+1 n+1 n+1 n+1
= number of white dots
= number of yellow dots

n
n
n
n
n
n

There are n(n+1) dots in the grid

n+1 n+1 n+1 n+1 n+1
= number of white dots
= number of yellow dots
n
n
n
n
n
n

Note = Q(# of terms · last term))

Gauss
∑i=1..n i = 1 + 2 + 3 + . . . + n
= Q(# of terms · last term)
Arithmetic Sum
True when ever terms increase slowly

∑i=0..n 2i = 1 + 2 + 4 + 8 +. . . + 2n
= ?
Geometric Sum

Geometric Sum

∑i=0..n 2i = 1 + 2 + 4 + 8 +. . . + 2n
= 2 · last term – 1
Geometric Sum

∑i=0..n ri = r0 + r1 + r2 +. . . + rn
= ?
Geometric Sum

S
Sr
r
r
r
.
.
.
r
r
S
Sr
1
r
S
r
1
r
1
2
3
n
n
1
n
1
n
1
=
1
r
r
r
.
.
.
2
3
r
n
+
+
+
+
+
=
+
+
+
+
+
–
=
–
=
–
–
+
+
+
Geometric Sum

∑i=0..n ri
r
1
r
1
n
1
=
–
–
+
Geometric Sum

When r>1?

∑i=0..n ri
r
1
r
1
n
1
=
–
–
+
Geometric Sum

= θ(rn)
Biggest Term

When r>1

∑i=0..n ri = r0 + r1 + r2 +. . . + rn
= Q(biggest term)

Geometric Increasing
True when ever terms increase quickly

∑i=0..n ri
=
Geometric Sum

When r<1? 1 r 1 r n 1 + - - ∑i=0..n ri = Geometric Sum 1 r 1 r n 1 + - - = θ(1) When r<1 Biggest Term ∑i=0..n ri = r0 + r1 + r2 +. . . + rn = Q(1) Bounded Tail True when ever terms decrease quickly ∑i=1..n 1/i = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + …+ 1/n = ? Harmonic Sum f(i) = 1 ∑i=1..n f(i) = n n Sum of Shrinking Function f(i) = ? ∑i=1..n f(i) = n1/2 n Sum of Shrinking Function f(i) = 1/2i ∑i=1..n f(i) = 2 ¥ Sum of Shrinking Function f(i) = 1/i ∑i=1..n f(i) = ? n Sum of Shrinking Function Harmonic Sum ∑i=1..n 1/i = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + …+ 1/n = Q(log(n)) Harmonic Sum Approximating Sum by Integrating The area under the curve approximates the sum ∑i=1..n f(i) ≈ ∫x=1..n f(x) dx Approximating Sum by Integrating 1/c+1 xc+1 d d x = xc ∫x=1..n xc dx = 1/c+1 nc+1 ∑i=1..n ic ≈ Arithmetic Sums = θ(# of terms · last term) True when ever terms increase slowly = θ(n·nc) Approximating Sum by Integrating 1/ln(b) eln(b)x d d x = eln(b)x = bx ∫x=1..n bx dx = 1/ln(b) bx ∑i=1..n bi ≈ Geometric Sums = θ(last term) True when ever terms increase quickly = θ(bn) Harmonic Sum Approximating Sum by Integrating Approximating Sum by Integrating Problem: Integrating may be hard too. Outline II) Math proofs of sums V) Ability to know the answer fast I) What is the sum Eg. ∑i=1..n f(i) = ∑i=1..n 1/i0.9999 =θ(n0.0001) III) Pattern of sums ∑i=1..n f(i) = θ(n · f(n)) IV) Intuition why this is the sum I flash it up If you follow great. If not don’t panic. Adding Made Easy We will now classify (most) functions f(i) into four classes: Geometric Like Arithmetic Like Harmonic Bounded Tail Adding Made Easy We will now classify (most) functions f(i) into four classes For each class, we will give an easy rule for approximating it’s sum θ( ∑i=1..n f(i) ) Classifying Animals Vertebrates Birds Mammals Reptiles Fish Dogs Giraffe Mammal Þ Complex social networks Dog Þ Man’s best friend Classifying Functions Functions Poly. Exp. 2θ(n) Þ ∑i=1..n f(i) = θ(f(n)) 8·2n / n100 + n3, θ(2n / n100) 8·2n + n3 nθ(1) 2θ(n) θ(2n) f(n) = 8·2n / n100 + n3 θ(2n / n100) Þ ∑i=1..n f(i) = θ(2n / n100) 20.5n < < 2n 8· 2n / n100 + n3 Significant Less significant Irrelevant Adding Made Easy 1 1 1 2 3 4 Four Classes of Functions Adding Made Easy If the terms f(i) grow sufficiently quickly, then the sum will be dominated by the largest term. Silly example: 1+2+3+4+5+ 1,000,000,000 ≈ 1,000,000,000 f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n)) Geometric Like: If the terms f(i) grow sufficiently quickly, then the sum will be dominated by the largest term. Classic example: ? f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n)) Geometric Like: If the terms f(i) grow sufficiently quickly, then the sum will be dominated by the largest term. Classic example: ∑i=1..n 2i = 2n+1-1 ≈ 2 f(n) f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n)) Geometric Like: If the terms f(i) grow sufficiently quickly, then the sum will be dominated by the largest term. For which functions f(i) is this true? How fast and how slow can it grow? f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n)) Geometric Like: r 1 r 1 n 1 = - - + = θ( ) r n Last Term when r>1.
∑i=1..n ri
1
r
r
r
.
.
.
2
3
r
n
+
+
+
+
+
=
= θ(f(n))
∑i=1..n (1.0001)i ≈ 10,000 (1.0001)n
= 10,000 f(n)
Lower Extreme:
Upper Extreme:
∑i=1..n (1000)i ≈ 1.001(1000)n
= 1.001 f(n)
Recall, when f(n) = ri = 2θ(n)
f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:

Because the constant is sooo big, the statement is just barely true.

∑i=1..n (1.0001)i ≈ 10,000 (1.0001)n
= 10,000 f(n)
Lower Extreme:
Upper Extreme:
∑i=1..n (1000)i ≈ 1.001(1000)n
= 1.001 f(n)
f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:

∑i=1..n (1.0001)i ≈ 10,000 (1.0001)n
= 10,000 f(n)
Lower Extreme:
Upper Extreme:
∑i=1..n (1000)i ≈ 1.001(1000)n
= 1.001 f(n)
Even bigger?

f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:

2n
2i
∑i=1..n 22 ≈ 22 = 1f(n)

No Upper Extreme:

Even bigger?
∑i=1..n (1.0001)i ≈ 10,000 (1.0001)n
= 10,000 f(n)
Lower Extreme:
f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:

2n
2i
∑i=1..n 22 ≈ 22 = 1f(n)

No Upper Extreme:
Functions in between?
∑i=1..n (1.0001)i ≈ 10,000 (1.0001)n
= 10,000 f(n)
Lower Extreme:
f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:

∑i=1..n 2i
= 2·2n –2
= 21 + 22 + 23 + 24 +…+ 2n
8·[ ]
8·
8·
8·
8·
8·
8·
= θ( 2n )

1100

2100

3100

4100

n100

i100

n100
+ i3
+ 13
+ 23
+ 33
+ 43
+ n3
+ n4
Dominated by the largest term.
= θ(f(n))

f(n) = 2n
8·

n100
+ n3
= θ( 2n )

n100
f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:

n100
≈

f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:
f(n) = 2n
8·

n100
∑i=1..n f(i)
f(n) £
£ c·f(n)
f(i) £ ?·f(n)
f(i) £ ?·f(i+1)
Easy
Hard
³
(1+1/i)100
1

2
1.9
=
8·2(i+1)

(i+1)100
f(i+1)
f(i)
8·2i

i100

=
³ 1/.51

£ .51·f(i+1)
f(i)

(i+1)100
i100

2
=

f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:
f(n) = 2n
8·

n100
∑i=1..n f(i)
f(n) £
£ c·f(n)
f(i) £ ?·f(n)
£ .512·f(i+2)
£ .51·f(i+1)
f(i)
£ .51·f(i+1)
f(i)
£ .513·f(i+3)
… £ .51(n-i)·f(i+(n-i))
= .51(n-i)·f(n)

f(i) £ .51(n-i)·f(n)

Eg. i = n, f(n) £ .51(n-n)·f(n) = 1·f(n)
i = 0, f(0) £ .51n·f(n)

f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:
f(n) = 2n
8·

n100
∑i=1..n f(i)
f(n) £
£ c·f(n)
∑i=1..n f(i) £ ∑i=1..n .51(n-i)·f(n)
= θ(1) · f(n)
f(i) £ ?·f(n)
£ .51·f(i+1)
f(i)

f(i) £ .51(n-i)·f(n)

= [∑i=1..n .51(n-i)] · f(n)

Functions
Poly.
Exp.
2θ(n) Þ ∑i=1..n f(i) = θ(f(n))
8·2n / n100 + n3

θ(2n / n100)
8·2n + n3
nθ(1)
2θ(n)
θ(2n)

f(n) = 8·2n / n100 + n3
θ(2n / n100)
Þ ∑i=1..n f(i) = θ(2n / n100)

f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:

If f(n) = c ban nd loge (n)
c Î ?
a Î ?
b Î ?
d Î ?
e Î ?
f(n) = Ω, θ ?
then ∑i=1..n f(i) = θ(f(n)).

³ 2Ω(n)
> 0
> 0
> 1
(-¥,¥)
(-¥,¥)

f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:

All functions in 2Ω(n)?
Maybe not.

f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:

Functions that oscillate continually
do not have the property.
f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:

Functions expressed with +, -, ×,  , exp, log
do not oscillate continually.
They are well behaved for sufficiently large n.
These do have the property.

f(i) ³ 2Ω(n) Þ ∑i=1..n f(i) = θ(f(n))
Geometric Like:

Adding Made Easy

Done

Adding Made Easy

If most of the terms f(i) have roughly the same value, then the sum is roughly the number of terms, n, times this value.

Silly example:
1,001 + 1,002 + 1,003 + 1,004 + 1,005
≈ 5 · 1,000
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

If most of the terms f(i) have roughly the same value, then the sum is roughly the number of terms, n, times this value.

Another silly example:
∑i=1..n 1 = n · 1
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

If most of the terms f(i) have roughly the same value, then the sum is roughly the number of terms, n, times this value.

Is the statement true for this function?

∑i=1..n i = 1 + 2 + 3 + . . . + n

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

If most of the terms f(i) have roughly the same value, then the sum is roughly the number of terms, n, times this value.

Is the statement true for this function?

∑i=1..n i = 1 + 2 + 3 + . . . + n
The terms are not roughly the same.

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

But half the terms are roughly the same.
∑i=1..n i =
1 + . . . + n/2 + . . . + n

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

But half the terms are roughly the same
and the sum is roughly the number
terms, n, times this value
∑i=1..n i =
1 + . . . + n/2 + . . . + n

∑i=1..n i = θ(n · n)
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Is the statement true for this function?

∑i=1..n i2 = 12 + 22 + 32 + . . . + n2
Even though, the terms
are not roughly the same.

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Again half the terms
are roughly the same.
∑i=1..n i =
12 + . . . + (n/2)2 + . . . + n2

1/4 n2

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Again half the terms
are roughly the same.
∑i=1..n i =
12 + . . . + (n/2)2 + . . . + n2

1/4 n2

∑i=1..n i2 = θ(n · n2)
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

∑i=1..n f(i)
≈ area under curve

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

area of small square
£ ∑i=1..n f(i)
≈ area under curve
£ area of big square

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

n/2 · f(n/2)
= area of small square
£ ∑i=1..n f(i)
≈ area under curve
£ area of big square
= n · f(n)

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

θ(n · f(n))
= n/2 · f(n/2)
= area of small square
£ ∑i=1..n f(i)
≈ area under curve
£ area of big square
= n · f(n)

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

θ(n · f(n))
= n/2 · f(n/2)
= area of small square
£ ∑i=1..n f(i)
≈ area under curve
£ area of big square
= n · f(n)

?
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

∑i=1..n i2 = 12 + 22 + 32 + . . . + n2
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:
f(i) = n2
f(n/2) = θ(f(n))

The key property is

= ?

The key property is

f(n/2) = (n/2)2 = 1/4 n2 = θ(n2) = θ(f(n))
∑i=1..n i2 = 12 + 22 + 32 + . . . + n2

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:
f(i) = n2
Þ = θ(n·f(n)) = θ(n · n2)

∑i=1..n f(i) = ?
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:
f(i) = nθ(1)

∑i=1..n ir = 1r + 2r + 3r + . . . + nr
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:
f(i) = nθ(1)
f(n/2) = θ(f(n))

The key property is

f(n/2) = (n/2)r = 1/2r nr = θ(nr) = θ(f(n))
∑i=1..n ir = 1r + 2r + 3r + . . . + nr

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:
Þ = θ(n·f(n)) = θ(n · nr)
f(i) = nθ(1)

∑i=1..n 2i = 21 + 22 + 23 + . . . + 2n
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:
f(i) = nθ(1)

f(n/2) = θ(f(n))

The key property is

The key property is
∑i=1..n 2i = 21 + 22 + 23 + . . . + 2n

f(n/2) = 2(n/2) = θ(2n) = θ(f(n))

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:
f(i) = nθ(1)

Þ = θ(n·f(n)) = θ(n · 2n)

∑i=1..n 1 = n · 1
= n · f(n)
Middle Extreme:
Upper Extreme:
∑i=1..n i1000 = 1/1001 n1001
= 1/1001 n · f(n)
All functions
in between.

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Adding Made Easy

Half done

f(i) = 1
∑i=1..n f(i) = n
n

Sum of Shrinking Function

f(i) = ?
∑i=1..n f(i) = n1/2
n
Sum of Shrinking Function
1/i1/2

f(i) = 1/i
∑i=1..n f(i) = log n
n
Sum of Shrinking Function

f(i) = 1/2i
∑i=1..n f(i) = 2
Sum of Shrinking Function
¥

If most of the terms f(i) have roughly the same value, then the sum is roughly the number of terms, n, times this value.

Does the statement hold
for functions f(i) that shrink?
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

If most of the terms f(i) have roughly the same value, then the sum is roughly the number of terms, n, times this value.

∑i=1..n 1/i = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … + 1/n
Does the statement hold
for the Harmonic Sum?
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Does the statement hold
for the Harmonic Sum?
∑i=1..n 1/i = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … + 1/n
∑i=1..n f(i) = ?
θ(n · f(n))

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Does the statement hold
for the Harmonic Sum?
∑i=1..n 1/i = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … + 1/n
∑i=1..n f(i)
θ(n · f(n))
= ∑i=1..n 1/i = ?

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Does the statement hold
for the Harmonic Sum?
∑i=1..n 1/i = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … + 1/n
∑i=1..n f(i)
θ(n · f(n))
= ∑i=1..n 1/i =
θ(log n)

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Does the statement hold
for the Harmonic Sum?
∑i=1..n 1/i = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … + 1/n
∑i=1..n f(i)
= θ(n · f(n))
= ∑i=1..n 1/i =
θ(log n)

?
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Does the statement hold
for the Harmonic Sum?
∑i=1..n 1/i = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … + 1/n
∑i=1..n f(i)
= θ(n · f(n))
= ∑i=1..n 1/i =
θ(log n)

θ(1) = θ(n · 1/n)
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Does the statement hold
for the Harmonic Sum?
∑i=1..n 1/i = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … + 1/n
∑i=1..n f(i)
= θ(n · f(n))
= ∑i=1..n 1/i =
θ(log n)
θ(1) = θ(n · 1/n)
≠
No the statement does not hold!
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Adding Made Easy

not included

Does the statement hold
for the almost Harmonic Sum?
∑i=1..n 1/i0.9999
Shrinks slightly slower
than harmonic.

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Does the statement hold
for the almost Harmonic Sum?
∑i=1..n 1/i0.9999
∑i=1..n f(i)
= θ(n · f(n))
= ∑i=1..n 1/i0.9999 =

?
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Does the statement hold
for the almost Harmonic Sum?
∑i=1..n 1/i0.9999
∑i=1..n f(i)
= θ(n · f(n))
= ∑i=1..n 1/i0.9999 =
θ(n0.0001)

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Does the statement hold
for the almost Harmonic Sum?
∑i=1..n 1/i0.9999
∑i=1..n f(i)
= θ(n · f(n))
= ∑i=1..n 1/i0.9999 =
θ(n0.0001)

?
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Does the statement hold
for the almost Harmonic Sum?
∑i=1..n 1/i0.9999
∑i=1..n f(i)
= θ(n · f(n))
= ∑i=1..n 1/i0.9999 =
θ(n0.0001)
θ(n0.0001) = θ(n · 1/n0.9999)
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Does the statement hold
for the almost Harmonic Sum?
∑i=1..n 1/i0.9999
∑i=1..n f(i)
= θ(n · f(n))
= ∑i=1..n 1/i0.9999 =
θ(n0.0001)
θ(n0.0001) = θ(n · 1/n0.9999)
=
The statement does hold!
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

∑i=1..n 1 = n · 1
= n · f(n)
Middle Extreme:
Lower Extreme:
∑i=1..n 1/i0.9999 = θ(n0.0001)
= θ(n · f(n))
All functions
in between.

f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

∑i=1..n 1 = n · 1
= n · f(n)
Middle Extreme:
Lower Extreme:
∑i=1..n 1/i0.9999 = θ(n0.0001)
= θ(n · f(n))
Upper Extreme:
∑i=1..n i1000 = 1/1001 n1001
= 1/1001 n · f(n)
f(i) = nθ(1)-1 Þ ∑i=1..n f(i) = θ(n·f(n))
Arithmetic Like:

Arithmetic Like
If f(n) = c ban nd loge (n)
c Î ?
a Î ?
b Î ?
d Î ?
e Î ?
f(n) = Ω, θ ?
then ∑i=1..n f(i) = θ(n · f(n)).

n-1+θ(1)
> 0
= 0
or b = 1
> -1
(-¥,¥)
(For +, -, ×,  , exp, log functions f(n))

Conclusion

Adding Made Easy

Done

Adding Made Easy

Harmonic

Harmonic Sum

∑i=1..n 1/i
= 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + …+ 1/n
= Q(log(n))

Adding Made Easy

If the terms f(i) decrease towards zero
sufficiently quickly,
then the sum will be a constant.

The classic example
∑i=0..n 1/2i = 1 + 1/2 + 1/4 + 1/8 + … = 2.

f(n) £ n-1-Ω(1) Þ ∑i=1..n f(i) = θ(1)
Bounded Tail:

If f(i) decays even faster, then the tail of the sum is more bounded.
2i
∑i=1..n 22 = θ(1).

f(n) £ n-1-Ω(1) Þ ∑i=1..n f(i) = θ(1)
Bounded Tail:

Upper Extreme:
∑i=1..n 1/i1.0001 = θ(1)

f(n) £ n-1-Ω(1) Þ ∑i=1..n f(i) = θ(1)
Bounded Tail:

Upper Extreme:
∑i=1..n 1/i1.0001 = θ(1)
No Lower Extreme:
2i
∑i=1..n 22 = θ(1).

All functions
in between.

f(n) £ n-1-Ω(1) Þ ∑i=1..n f(i) = θ(1)
Bounded Tail:

Bounded Tail
If f(n) = c ban nd loge (n)
c Î ?
a Î ?
b Î ?
d Î ?
e Î ?
f(n) = Ω, θ ?
then ∑i=1..n f(i) = θ(1).

> 0
< 0 (-¥,¥) (-¥,¥) Conclusion or b < 1 c nd loge (n) c > 0
a > 0
b > 1

ban

Bounded Tail
If f(n) = c nd loge (n)
c Î ?
a = 0
b = 1
d Î ?
e Î ?
f(n) = Ω, θ ?
then ∑i=1..n f(i) = θ(1).

= n-1-Ω(1)
> 0
< -1 (-¥,¥) Conclusion Adding Made Easy Done Adding Made Easy Missing Functions 1/nlogn logn/n Adding Made Easy Geometric Like: If f(n) ³ 2Ω(n), then ∑i=1..n f(i) = θ(f(n)). Arithmetic Like: If f(n) = nθ(1)-1, then ∑i=1..n f(i) = θ(n · f(n)). Harmonic: If f(n) = 1/n , then ∑i=1..n f(i) = logen + θ(1). Bounded Tail: If f(n) £ n-1-Ω(1), then ∑i=1..n f(i) = θ(1). (For +, -, ×,  , exp, log functions f(n)) This may seem confusing, but it is really not. It should help you compute most sums easily. Recurrence Relations T(1) = 1 T(n) = a T(n/b) + f(n) Recurrence Relations » Time of Recursive Program Recurrence relations arise from the timing of recursive programs. Let T(n) be the # of “Hi”s on an input of “size” n. procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) ? Given size 1, the program outputs T(1)=1 Hi’s. Recurrence Relations » Time of Recursive Program procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) Given size n, the stackframe outputs f(n) Hi’s. Recurrence Relations » Time of Recursive Program procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) Recursing on an instances of size n/b generates T(n/b) “Hi”s. Recurrence Relations » Time of Recursive Program procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) Recursing a times generates a·T(n/b) “Hi”s. Recurrence Relations » Time of Recursive Program procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) For a total of T(1) = 1 T(n) = a·T(n/b) + f(n) “Hi”s. Recurrence Relations » Time of Recursive Program procedure Eg(In) n = |In| if(n£1) then put “Hi” else loop i=1..f(n) put “Hi” loop i=1..a In/b = In cut in b pieces Eg(In/b) Solving Technique 1 Guess and Verify Recurrence Relation: T(1) = 1 & T(n) = 4T(n/2) + n Guess: G(n) = 2n2 – n Verify: Left Hand Side Right Hand Side T(1) = 2(1)2 – 1 T(n) = 2n2 – n 1 4T(n/2) + n = 4 [2(n/2)2 – (n/2)] + n = 2n2 – n Recurrence Relation: T(1) = 1 & T(n) = 4T(n/2) + n Guess: G(n) = an2 + bn + c Verify: Left Hand Side Right Hand Side T(1) = a+b+c T(n) = an2 +bn+c 1 4T(n/2) + n = 4 [a (n/2)2 + b (n/2) +c] + n = an2 +(2b+1)n + 4c Solving Technique 2 Guess Form and Calculate Coefficients Recurrence Relation: T(1) = 1 & T(n) = 4T(n/2) + n Guess: G(n) = an2 + bn + 0 Verify: Left Hand Side Right Hand Side T(1) = a+b+c T(n) = an2 +bn+c 1 4T(n/2) + n = 4 [a (n/2)2 + b (n/2) +c] + n = an2 +(2b+1)n + 4c Solving Technique 2 Guess Form and Calculate Coefficients c=4c c=0 Recurrence Relation: T(1) = 1 & T(n) = 4T(n/2) + n Guess: G(n) = an2 - 1n + 0 Verify: Left Hand Side Right Hand Side T(1) = a+b+c T(n) = an2 +bn+c 1 4T(n/2) + n = 4 [a (n/2)2 + b (n/2) +c] + n = an2 +(2b+1)n + 4c Solving Technique 2 Guess Form and Calculate Coefficients b=2b+1 b=-1 Recurrence Relation: T(1) = 1 & T(n) = 4T(n/2) + n Guess: G(n) = an2 - 1n + 0 Verify: Left Hand Side Right Hand Side T(1) = a+b+c T(n) = an2 +bn+c 1 4T(n/2) + n = 4 [a (n/2)2 + b (n/2) +c] + n = an2 +(2b+1)n + 4c Solving Technique 2 Guess Form and Calculate Coefficients a=a Recurrence Relation: T(1) = 1 & T(n) = 4T(n/2) + n Guess: G(n) = 2n2 - 1n + 0 Verify: Left Hand Side Right Hand Side T(1) = a+b+c T(n) = an2 +bn+c 1 4T(n/2) + n = 4 [a (n/2)2 + b (n/2) +c] + n = an2 +(2b+1)n + 4c Solving Technique 2 Guess Form and Calculate Coefficients a+b+c=1 a-1+0=1 a=2 Recurrence Relation: T(1) = 1 & T(n) = aT(n/b) + f(n) Solving Technique 3 Approximate Form and Calculate Exponent which is bigger? Guess Recurrence Relation: T(1) = 1 & T(n) = aT(n/b) + f(n) Guess: aT(n/b) << f(n) Simplify: T(n) » f(n) Solving Technique 3 Calculate Exponent In this case, the answer is easy. T(n) = Q(f(n)) Recurrence Relation: T(1) = 1 & T(n) = aT(n/b) + f(n) Guess: aT(n/b) >> f(n)
Simplify: T(n) » aT(n/b)
Solving Technique 3
Calculate Exponent
In this case, the answer is harder.

Recurrence Relation:
T(1) = 1 & T(n) = aT(n/b)
Guess: G(n) = cna
Verify:
Left Hand Side Right Hand Side
T(n)
= cna aT(n/b)
= a [c (n/b) a ]
= c a b-a na

Solving Technique 3
Calculate Exponent
(log a/log b)
= cn
1 = a b-a
ba = a
a log b = log a
a = log a/log b

Recurrence Relation:
T(1) = 1 & T(n) = 4T(n/2)
Guess: G(n) = cna
Verify:
Left Hand Side Right Hand Side
T(n)
= cna aT(n/b) + f(n)
= c [a (n/b) a ]
= c a b-a na

Solving Technique 3
Calculate Exponent
1 = a b-a
ba = a
a log b = log a
a = log a/log b

(log a/log b)
= cn
(log 4/log 2)
= cn
2
= cn

Logs
log 27
log 9

Logs
log? 27
log? 9

=
Which base?

Logs
log2 27
log2 9

=
It does not matter.
log2 c
log2 c

· logc 27
· logc 9

=
logc 27
logc 9

Which is easiest?

Logs
log3 27
log3 9

=
log3 33
log3 32

=
3
2

Please no calculators in exams.
And I wont ask
log 25
log 9

Recurrence Relation:
Solving Technique 3
Calculate Exponent
If bigger then

T(n) = Q(f(n))
If bigger then
(log a/log b)
T(n) = Q(n )
And if aT(n/b) » f(n)
what is T(n) then?

T(1) = 1 & T(n) = aT(n/b) + f(n)

4: Decorate The Tree
T(n) = a T(n/b) + f(n)
T(1) = 1 & T(n) = aT(n/b) + f(n)
f(n)
T(n/b)
T(n/b)
T(n/b)
T(n/b)
T(n)
=
T(1)
T(1) = 1
1
=

f(n)
T(n/b)
T(n/b)
T(n/b)
T(n/b)
T(n)
=
a

f(n)
T(n/b)
T(n/b)
T(n/b)
T(n)
=
a

f(n/b)
T(n/b2)
T(n/b2)
T(n/ b2)
T(n/ b2)

f(n)
T(n)
=
a

f(n/b)
T(n/b2)
T(n/b2)
T(n/ b2)
T(n/ b2)

a
f(n/b)
T(n/b2)
T(n/b2)
T(n/ b2)
T(n/ b2)

11111111111111111111111111111111 . . . . . . 111111111111111111111111111111111
f(n)
T(n)
=
a

f(n/b)
T(n/b2)
T(n/b2)
T(n/ b2)
T(n/ b2)

a
f(n/b)
T(n/b2)
T(n/b2)
T(n/ b2)
T(n/ b2)

Evaluating: T(n) = aT(n/b)+f(n)
Level

0
1
2

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size

0
1
2

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size

0 n
1
2

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size

0 n
1 n/b
2

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size

0 n
1 n/b
2 n/b2

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size

0 n
1 n/b
2 n/b2

i n/bi

h n/bh

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size

0 n
1 n/b
2 n/b2

i n/bi

h n/bh

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size

0 n
1 n/b
2 n/b2

i n/bi

h n/bh = 1

base case

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size

0 n
1 n/b
2 n/b2

i n/bi

h n/bh = 1

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size

0 n
1 n/b
2 n/b2

i n/bi

h = log n/log b n/bh = 1

bh = n
h log b = log n
h = log n/log b

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame
0 n
1 n/b
2 n/b2

i n/bi

h = log n/log b 1

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame
0 n f(n)
1 n/b f(n/b)
2 n/b2 f(n/b2)

i n/bi f(n/bi)

h = log n/log b 1 T(1)

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames
0 n f(n)
1 n/b f(n/b)
2 n/b2 f(n/b2)

i n/bi f(n/bi)

h = log n/log b n/bh T(1)

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames
0 n f(n) 1
1 n/b f(n/b) a
2 n/b2 f(n/b2) a2

i n/bi f(n/bi) ai

h = log n/log b n/bh T(1) ah

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames
0 n f(n) 1
1 n/b f(n/b) a
2 n/b2 f(n/b2) a2

i n/bi f(n/bi) ai

h = log n/log b n/bh T(1) ah

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames
0 n f(n) 1
1 n/b f(n/b) a
2 n/b2 f(n/b2) a2

i n/bi f(n/bi) ai

h = log n/log b n/bh T(1) ah

ah = a

= n
log n/log b
log a/log b

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames Work in Level
0 n f(n) 1
1 n/b f(n/b) a
2 n/b2 f(n/b2) a2

i n/bi f(n/bi) ai

h = log n/log b n/bh T(1)

n
log a/log b

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames Work in Level
0 n f(n) 1 1 · f(n)
1 n/b f(n/b) a a · f(n/b)
2 n/b2 f(n/b2) a2 a2 · f(n/b2)

i n/bi f(n/bi) ai ai · f(n/bi)

h = log n/log b n/bh T(1)

n
log a/log b
n · T(1)
log a/log b
Total Work T(n) = ∑i=0..h ai×f(n/bi)

Evaluating: T(n) = aT(n/b)+f(n)
= ∑i=0..h ai×f(n/bi)

If a Geometric Sum
∑i=0..n xi = θ(max(first term, last term))

Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames Work in Level
0 n f(n) 1 1 · f(n)
1 n/b f(n/b) a a · f(n/b)
2 n/b2 f(n/b2) a2 a2 · f(n/b2)

i n/bi f(n/bi) ai ai · f(n/bi)

h = log n/log b n/bh T(1)

n
log a/log b
n · T(1)
log a/log b

Dominated by Top Level or Base Cases

Evaluating: T(n) = aT(n/b)+f(n)
Is the sum Geometric?
Simplify by letting f(n) = nc logkn
T(n) = ∑i=0..h ai×f(n/bi)
= ∑i=0..h ai×(n/bi)c ×logk(n/bi)
= nc ∑i=0..h 2[log a – c log b] · i ×logk(n/bi)
Geometrically Increasing
Arithmetic Sum
Geometrically Decreasing
Sum = θ(last term)
= θ( )
Sum = θ(any term ×# terms)
= θ(f(n) × log n)
Sum = θ(first term)
= θ(f(n)).
log a – c log b > 0
log a – c log b = 0
log a – c log b < 0 c < log a/log b c = log a/log b & k<-1 c = log a/log b & k>-1
c > log a/log b

n
log a/log b
(n/..)c = nc
ai = 2[log a]·i
(../bi)c = 2[-c log b]·i
= nc ∑i=0..h 2-d i ×logk(n/bi)

n
log a/log b
k=-1 Þ logk(n/bi)
= 1/(logn – i × logb)
» 1/i (backwards)
= nc ∑i=0..h 20 i ×logk(n/bi)

(back wards)

n
log a/log b
= nc ∑i=0..h 2+d i ×logk(n/bi)

Evaluating: T(n) = 4T(n/2)+ n3/log5n

Time for top level?:

Evaluating: T(n) = 4T(n/2)+ n3/log5n

Time for top level: f(n) = n3/log5n
Time for base cases?:

Evaluating: T(n) = 4T(n/2)+ n3/log5n

Time for top level: f(n) = n3 /log5n
Time for base cases:

Evaluating: T(n) = 4T(n/2)+ n3/log5n
θ(n ) =
log a/log b
θ(n )
log ?/log ?

Time for top level: f(n) = n3 /log5n
Time for base cases:

Evaluating: T(n) = 4T(n/2)+ n3/log5n
θ(n ) =
log a/log b
θ(n ) = ?
log 4/log 2

Time for top level: f(n) = n3/log5n
Time for base cases:
Dominated?: c = ?
Evaluating: T(n) = 4T(n/2)+ n3/log5n
θ(n ) =
log a/log b
θ(n ) = θ(n2)
log 4/log 2
log a/log b = ?