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.
