Performance Analysis


Posted by clins210 on 2020-11-17

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.


#complexity #Time #space #big-O #omega







Related Posts

PHP會員管理系統 - CRUD概念 & 前後端分離介面

PHP會員管理系統 - CRUD概念 & 前後端分離介面

CS75 (Summer 2012) Lecture 9 Scalability Harvard Web Development David Malan

CS75 (Summer 2012) Lecture 9 Scalability Harvard Web Development David Malan

JavaScript 程式執行原理:hw2:Event Loop + Scope

JavaScript 程式執行原理:hw2:Event Loop + Scope


Comments