두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n >= K에 대하여 f(n) <= Cg(n)을 만족하는 두 개의 상수 C와 K가 존재한다면, f(n)의 빅-오는 O(g(n)) 이다.
* f(n) = 5n^2 + 100
* g(n) = n^2
이 상황에서 f(n) <= Cg(n)을 만족시키기 위한 C를 구해보자, (단 C=3500, n >= 12 꼭 12가 아니여도 된다 적당한수를 정하였다.)
위 가정을 대입해보면
f(n) <= Cg(n) => 5n^2 + 100 <= 3500 * n^2
빅-오의 정의에 해당하는 C와 K가 3500, 12로 각각 존재하니 5*n^2 + 100의 빅-오는 n^2이다.
f(n) = 5 * n^2 + 100 => O(n^2)
지금까지 전개한 내용을 빅-오의 정의와 연결시켜 보면
"두 개의 함수 f(n)과 g(n)이 주어졌을 때"
=> 두 개의 함수 f(n) = 5 * n^2 + 100, g(n) = n^2이 주어졌을 때
"모든 n >= K에 대하여"
=> 모든 n >= 12 에 대하여,
"f(n) <= Cg(n)을 만족하는 두 개의 상수 C와 K가 존재하면"
=> 5 * n^2 + 100 <= 3500 * n^2 을 만족하는 3500(C)과 12(K)가 존재하니,
"f(n)의 빅-오는 O(g(n))이다"
=> 5 * n^2 + 100 의 빅-오는 O(n^2) 이다.
상수 C와 K를 크게 잡아도 될까? n >= K 에 대하여 f(n) <= Cg(n)을 만족시킨다는 것에 무슨 의미가 있을가?
먼저 K값에 대해서 보자면, f(n) <= Cg(n)를 만족하는데 있어서 n>=K라는 식의 범위젱한을 둔 이유는 다음과 같다.
"n이 계속 커진다. 그러다가 어느 순간 이후부터 f(n) <= Cg(n)을 항상 만족하기만 하면 된다."
즉, 빅-오를 판별하는데 있어서 f(n) <= Cg(n)을 만족하는 n의 값은 중요하지 않다. 중요한 것은 n의 값이 계속해서 커지면서 어느 순간부터는 f(n) <= Cg(n)에서 C를 크게 잡아도 상관없는 이유는 무엇일까? 이는 다음의 빅-오 판별결과를 가지고 이야기하겠다.
"5 * n^2 + 100의 빅-오는 O(n^2)이다."
이는 다음의 뜻으로 해석할 수 있다.
"5 * n^2 + 100 가 연산횟수의 증가율이 크다고 한들 증가율의 패턴이 n^2를 넘지 못한다."
즉, 빅-오는 증가율의 상한선을 표현하는 표기법이다! 따라서 "~의 증가율 패턴을 넘지 못한다." 라는 것을 증명하기 위해서, n^2의 증가율 패턴을 보이면서 C가 큰 수식을 만드는 것이다.
