Space = fixed part + variable part: S(P)=c+Sp (c = code/constants, Sp = instance characteristics). Time T(P)=compile time+run time; run time = sum of instruction times for the instance.
The operation contributing most to total time, usually in the innermost loop. T(n) ~ cop x C(n), cop = time per basic op, C(n) = number of executions.
Worst = longest input of size n (sequential search n). Best = fastest input (1). Average = typical input with a probability distribution: Cavg(n)=p(n+1)/2+(1-p)n. Amortized = total for n ops is much better than n x worst-case of one. Average is not the average of best and worst.
Framework: input size -> units for running time -> orders of growth -> worst/best/average. Size examples: list length; matrix order; characters/words. Count basic-operation executions instead of seconds.
Size n, op = comparison, no case variation: C(n)=n-1 -> Theta(n).
Worst case (all distinct): C(n)=(n-1)n/2 -> Theta(n^2).
Size = order n, op = multiplication: M(n)=n^3 -> Theta(n^3).
Operation is the comparison n>1; n halves each time -> floor(log2 n)+1 -> Theta(log n).
M(n)=M(n-1)+1, M(0)=0 -> M(n)=n -> Theta(n).
M(n)=2M(n-1)+1, M(1)=1 -> M(n)=2^n-1 -> Theta(2^n). n=3 gives 7 moves.