Efficiency and Correctness

Efficienct analysis
=> Algorithm analysis

Correctness analysis
=> Using a mathmatical proof ( 실제로 타당한가 여부 조사)
※Incorrect : loop, wrong answer.

Big O
=> g(n) ≤ c x f(n)
=> c : some positive real constant
=> n : some non-negative integer
=> g(n) ∈ O(f(n))
ex) 3lgn, 4n^2, 5n+7 ∈ O(n^2)

Omega Ω
=> g(n) ≥ c x f(n)
=> c : some positive real constant
=> n : some non-negative integer
=> g(n) ∈ Ω(f(n))
ex) 4n^2, 4n^3, 2^n, n!, n^n ∈ Ω(n^2)

Theta Θ
=> c x f(n) ≤ g(n) ≤ d x f(n)
=> c, d : some positive real constant
=> n : some non-negative integer
=> g(n) ∈ Θ(f(n))
ex) 4n^2, 4n^2 + 7, n^2 ∈ Θ(n^2)

Small o
=> g(n) ≤ c x f(n)
=> c : Every positive real constant
=> n : some non-negative integer
=> g(n) ∈ o(f(n))
ex) n, logn, nlogn ∈ o(n^2)

Properties of Order Functions
-  g(n) ∈ O(f(n)) iff f(n) ∈ Ω(g(n) 
-  g(n) ∈ Θ(f(n)) iif  f(n) ∈ Θ(g(n))
- If b>1 and a>1, then logaN ∈Θ(logbN)
- If b>a>0, then a^n ∈ o(b^n)
- For all a>0, a^n ∈ o(n!)
- If c ≥ 0, d ≥ 0, g(n)  ∈ O(f(n)), and h(n)  ∈ Θ(f(n)), then {c x g(n) + d x h(n)} ∈ Θ(f(n)