Day3

Big-O notation

---

O : <=

Ω : >=

θ : =

o : < 

ω : >

T(n)∈O(n^2)

T(n)∈Ω(n)

---

g(n)∈O(f(n)), if there exists some positive real constant c

and some non-negative integer N

such that for all n>=N, g(n)<=cf(n)

;

ex) 3n^2+2n+1∈O(n^2)

3n^2+2n+1<=3n^2+2n^2+n^2=6n^2 for all n>=1

2n+1∈O(n)

• If g(n)∈O(f(n)), then f(n)∈Ω(g(n))
• g(n)∈θ(f(n)) iff g(n)∈O(f(n)) and g(n)∈Ω(f(n))

g(n)∈o(f(n)), if there exists some non-negative N

for every positive real constant c such that for all n>=N g(n)<=cf(n)

If g(n)∈o(f(n)), then f(n)∈ω(g(n))

ex) n^2∈o(n^3)

n^2∈O(n^2)

n^2∈O(n^3)

n^2 not∈ o(n^2)

• If lim n->무한 g(n)/f(n)=0, g(n)∈o(f(n)) n이 커질수록 g(n)과 f(n)의 차이가 커진다.
• If lim n->무한 g(n)/f(n)=c, g(n)∈θ(f(n)) n이 커질수록 g(n)과 f(n)의 차이가 작아진다.

Some properties

f1∈O(g1) and f2∈O(g2) -> f1f2∈O(g1g2)

    -> f1+f2∈O(|g1|+|g2|)

• o(f)+o(f)⊆o(f)
• o(f)*o(g)⊆o(fg)
• o(o(f))⊆o(f)

---

ㅇO(1

O(1), O(logn), O(n), O(nlogn), O(n^2),..., O(2^n)

T(n)∈O(n^k) polynomial time algorithm

얘보다 작으면 더 효율적

ex) O(logn), O(nlogn)

exponential->비효율적 ex) O(2^n)

small o관계가 있다??