English Music Poem
Math Notes
3.3
Find max (a_0, a_1, a_2,........a_n-1: integers)
Max= a_0
Procedure Linear-search(a_1,...,a_n-1: integers, target: integer)
For i=0 to n-1
If target =a
Return true
Return False
n=# of comparisons
Target = a_i
Once each time through loop 9c through loop n times
n comparisons
Loop book keeping
i=0 to n-1
i=0 0<= n-1
i=1 1<= n-1
“
“
“
N-1 n-1 <= n-1
n n<=n-1
Buuble sort
For i = 1 to n <--------------|
For j = 0 to n-2 |-----Do the inside part n times
If aj > aj + 1 |
Return (a_0, a_1, a_n-1)<---|
Inside for i = 1 to n loop
For j = 0 to n-2 loop bookkeeping
If aj > aj + 1 do this for each j value n-1 j value n-1 comparisons
i=1 we do 2n-1 comp
i=2 we do 2n-1 comp
i=3 we do 2n-1 comp
i=n we do 2n-1 comp
Total # of loops: n(n+1) + n+1
2n^2 is O(n^2)
Binary search
List has 8 elements
While (high - low > 1)
If target < a mid)
Return target = T/F
8.3/7.3 Big theta fov reclusive algorithms
T_n= # of more to relocate an n disk tower
T_5= T_4 + 1 + T_4 T_n= 2T_n-1 + 1 n>1
T_1= 1
Merge sort At worst, merging takes n-1 comps + bookkeeping
M_n = # of comparison to sort a list of size n. N+1
M_n = M_n/2 + M_n/2 + (n-1) + (2n) + (n+1)
M_n = 2*M_n/2 + 4n
Recursive Binary Search
BS_n = # of comp, for binary search
BS_n = BS_n/2 + 1(Which list to look at) + 1 (see if list size >1)
BS_n = BS_n/2 +2
FM_n = # of comps needed for recursive find - max.
FM_n = FM_n/2 + FM_n/2 + 1
FM_n = 2FM_n/2 + 1
General:
F(n) = a*f(b*n) + g(n)
F(n) = a*f(n/b) + c*n^d
Mase Them theorem
{ theta(n^d)if a<b^d
F(n)= { Theta(n^d Logn)if a = b^d
{ Theta(n^(log_b(a)))if a > b^d
Example:
MS_n = 2MS_n/2 + 4n
F(n) = a*f(n/b) + C*n^d
a=2
b=2
c=4
d=1
a b^d
“
2 = 2^1
Theta (n^d Logn)
Example: Binary search
BS_n= 1*BS_n/2 + 2
F(n) = a*f(n/2) + c*n^d
a=1
b=2
c=2
d=0
a b^d
“ “
1 = 2^0
Theta (n^d logn)
Theta(logn)
Example:
FM_n = 2FM_n/2 + 1
F(n) = a*f(n/2) + c*n^d
a=2
b=2
c=1
d=0
a b^d
“ “
2 > 2^0
Theta( n^(Log_b(a)))
Theta(n^(log_2(2)))
Theta(n)
3.3
Find max (a_0, a_1, a_2,........a_n-1: integers)
Max= a_0
Procedure Linear-search(a_1,...,a_n-1: integers, target: integer)
For i=0 to n-1
If target =a
Return true
Return False
n=# of comparisons
Target = a_i
Once each time through loop 9c through loop n times
n comparisons
Loop book keeping
i=0 to n-1
i=0 0<= n-1
i=1 1<= n-1
“
“
“
N-1 n-1 <= n-1
n n<=n-1
Buuble sort
For i = 1 to n <--------------|
For j = 0 to n-2 |-----Do the inside part n times
If aj > aj + 1 |
Return (a_0, a_1, a_n-1)<---|
Inside for i = 1 to n loop
For j = 0 to n-2 loop bookkeeping
If aj > aj + 1 do this for each j value n-1 j value n-1 comparisons
i=1 we do 2n-1 comp
i=2 we do 2n-1 comp
i=3 we do 2n-1 comp
i=n we do 2n-1 comp
Total # of loops: n(n+1) + n+1
2n^2 is O(n^2)
Binary search
List has 8 elements
While (high - low > 1)
If target < a mid)
Return target = T/F
8.3/7.3 Big theta fov reclusive algorithms
T_n= # of more to relocate an n disk tower
T_5= T_4 + 1 + T_4 T_n= 2T_n-1 + 1 n>1
T_1= 1
Merge sort At worst, merging takes n-1 comps + bookkeeping
M_n = # of comparison to sort a list of size n. N+1
M_n = M_n/2 + M_n/2 + (n-1) + (2n) + (n+1)
M_n = 2*M_n/2 + 4n
Recursive Binary Search
BS_n = # of comp, for binary search
BS_n = BS_n/2 + 1(Which list to look at) + 1 (see if list size >1)
BS_n = BS_n/2 +2
FM_n = # of comps needed for recursive find - max.
FM_n = FM_n/2 + FM_n/2 + 1
FM_n = 2FM_n/2 + 1
General:
F(n) = a*f(b*n) + g(n)
F(n) = a*f(n/b) + c*n^d
Mase Them theorem
{ theta(n^d)if a<b^d
F(n)= { Theta(n^d Logn)if a = b^d
{ Theta(n^(log_b(a)))if a > b^d
Example:
MS_n = 2MS_n/2 + 4n
F(n) = a*f(n/b) + C*n^d
a=2
b=2
c=4
d=1
a b^d
“
2 = 2^1
Theta (n^d Logn)
Example: Binary search
BS_n= 1*BS_n/2 + 2
F(n) = a*f(n/2) + c*n^d
a=1
b=2
c=2
d=0
a b^d
“ “
1 = 2^0
Theta (n^d logn)
Theta(logn)
Example:
FM_n = 2FM_n/2 + 1
F(n) = a*f(n/2) + c*n^d
a=2
b=2
c=1
d=0
a b^d
“ “
2 > 2^0
Theta( n^(Log_b(a)))
Theta(n^(log_2(2)))
Theta(n)
English Persona Poem