Def:

(Worst case) Complexity of a problem is the min number of operations needed to solve the problem in the worst case using particular resources.

eg. Matrix Multiplication
$C_{nn}=A_{\mbox{n x n} }*B_{\mbox{n x n}}$
$C_{ij}=A_{i1}B_{1j}+A_{i2}B_{2j}+\cdots +A_{in}B_{nj}$

for $i \leftarrow$ 1 to $n$
for $j \leftarrow$ 1 to $n$

$C_{ij}\leftarrow 0$

for $k\leftarrow 1$ to $n$
$C_{ij}=C_{ij}+A_{ik}B_{kj}$

• Basic operation: Multiplication (addition can be ignored)
• $W(n)=n^{3}$
• lower bound on number of multiplications $=n^{2}$
  lower bound on the problem complexity of matrix multiplication = $n^2$.
• best algorithm found has time complexity $n^{2.367}$

Average-Case Problem Complexity

Space complexity of a problem

• matrix multiplication $O(1)$
• sorting on comparison model $O(1)$.
• matching parentheses $O(n)$.