Resources consumed: time and space
2.1 在链表中找一个元素
3-6
最差的情况是找不到这个元素，最差时间复杂度为n
最好的情况是我们要找的数就在第一个位置，时间复杂度为1
判断时间复杂度需要考虑的最重要因素是找到basic operation并判断它运行了多少次
运行时间为t(n)=c*g(n),c是basic operation运行一次所花的时间，g(n)是basic operation运行的次数
3-11
Worse case: analysis makes the most pessimistic assumptions about the input
Best case: analysis makes the most optimistic assumptions about the input
Average case: analysis aims to find the expected running time across all possible input of size n (Note: not an average of the worst and best cases)
Amortised analysis takes context of running an algorithm into account, calculates cost spread over many runs. Used for “self-organising” data structures that adapt to their usage
3-14
n^-1/2 < log n < n^1/3< n^1/2<n<n log n<n^2 <n^3 <2^n
linear/linearithmic/quadratic/cubic/exponential/factorial
在考虑增长速率的时候不考虑常数和很小的输入值，尽量将输入值往大的考虑
求增长速率的两种方法：直接相除/求导相除
3-18/4-6
4-3
如果f属于Theta(n),它也属于O(n)
2.2 在链表中找最大元素
4-7 复杂度为n
)
2.3 Selection Sort
4-13 复杂度为n^2
2.4 Matrix Multiplication
4-15 复杂度为n^3
2.5 telescoping/backward substitution
4-20
2.6 Euclid
4-27 复杂度为O(log(m+n))
4-28
4-29 Some Useful Formulas
