Algorithms and Complexity Analysis

We are only concern with Running Time

Just to this and move on

Optimization Of Code (BIG O).pdf

Complexity Analysis (BIG O)2.pdf

Running Time

Measuring Running Time

Calculating Complexity of Algorithm

Statement Operations Iterations Sub-Total (Operations x iterations)
1 2 1 2 * 1 = 2
2a 1 1 1 * 1 = 1
2b 1 n 1 * n = n
2c 2 n - 1 2 * (n - 1) = 2n - 2
3 3 n - 1 3 * (n - 1) = 3n - 3
4 1 1 1 * 1
$Complexity = 2 + 1 + n + 2n - 2 + 3n - 3 + 1 = 6n - 1$

Best / Worst / Average cases

MIT_BIGo.png

MIT_BIGo2.png

Complexity Analysis

sum = 0
for i = 1 to i = n
	for j = 1 to j = n
		sum++
return sum
Statement Operations Iterations Sub-Total
1 1 1 1
2a 1 1
2b 1 n + 1 n + 1
2c 2 n 2n
3a 1 n * 1 n
3b 1 n(n + 1) n^2 + n
3c 2 n(n) 2n^ 2
4 2 n(n) 2n^ 2
5 1 1 1
$1 + 1 + n + 1 + 2n + n + n^2 + n + 2n^2 + 2n^2 + 1$ $5n^2 + 5n + 4$