L(n) = log(n!) for theta (n*log(n))
= log 1 + log 2 + log 3 ... log n
bounded upper by n log(n) -> big O(n log(n))
is it possible to bound it by O (n log n/2 + 1) instead of n log n? yes, but n log n is sufficient
drop smallest not the largest -> general rule for
instead of
(n-1) log (n) use n log n - log (1)
log(i+1) + log(i+2) ... log(n)
.>= log(i+1) ... log(i+1) (n-1 terms in this set)
L(n) >= (n-i) log (i+1) for any 1 <= i <= n
L(n) for theta (n log(n)) >= n/2 log (n/2 +1)
Function aprox to n^(k+1) / k + 1 S(n,k) =
1^k + 2^k + ... + n^k
integral(x^k dx)|n,0
= n^k+1 / k + 1 |n,0
= n^k / k+1
when having an integral that looks simmilar to your function, use sandwiching otherwise, use upper and lower limits
y = f(x) = f(x) = x^k
area under curve on board = integral(x^k dx)|n,0 = n^k+1 / k+1
board displays riemann sum (left and right) from 0 ... n where x is moving towards n
g_a is red, g_b is blue
g_b (x) <= x^k <= g_a(x)
figure out the road map from left hand side to right hand side
red area is S(n+1,k) blue is S(n-1,k)
from this we can see that this is asymtotically equivalant
S(n,k) / (n^k+1 / k+1) <= (n^k+1/k+1 + n^k) / (n^k+1 / k+1)
1 <= S(n,k)/(n^k+1 / k+1) = 1+(k+1 / n)
not expected to get answer without the whole equation
n log(n) vs
undercounting vs overcounting for the riemann sum in this course we have a sum we approximate with integrals, instead of integrals
Monday after memorial day HW: 1st question is on euclidian algorithm, polynomial computation, worst case, best case scenario Format of quiz: on campus, short questions 15 min 4 questions, 10 min 3 question, fill in the blanks, multiple answers, match questions
Assignment 1 will be covered in quiz 1