Performance Analysis

Complexity theory

Space complexity

S(P) = c + Sp(l)
Run execution time

Time complexity

T(P) = c + Tp(l)
c = compiling time

lesat upper Bound: big-O

f(n) = O (g(n)) iff
∃ positive cons. and n0 =>
f(n) <= c g(n)
∀ n, n >= n0.

ex(1). 3n + 2 = O(n) 3n + 2 <= 4n, (n >= 2)
ex(2). 10n^2 + 4n + 2 = O(n^2) 10n^2 + 4n + 2 <= 11 n^2
ex(3). 3n + 2 = O(n^2) 3n + 2 <= n^2, (n >= 4)

most lower Bound: Ω

f(n) = Ω (g(n)) iff
∃ positive cons. and n0 =>
f(n) >= c g(n)
∀ n, n >= n0.

lesat upper Bound: Θ

f(n) = Θ (g(n)) iff
∃ positive cons. c1,c2,and n0 =>
c1 g(n) <= f(n) <= c2 g(n)
∀ n, n >= n0.