점근 표기법

Question

이것은 알고리즘에 MIT OpenCourse 소개의 할당에서 점근 표기법에 문제가 다음 문장 각각에 대해
, 그것은 여부를 결정 항상 참, 결코 진정한, 또는 때때로 true asymptotically nonnegative functions f 및 g입니다. 항상 true 또는 이 아닌 경우 이유를 설명하십시오. 가끔 true 인 경우 인 경우, 하나의 예가 true이고 하나는 false입니다.

f(n) ≠ O(g(n)) and g(n) ≠ O(f(n)) (both are Big-O notes) 

가 나는 결코 사실 생각합니다. 여기에 내 증거가있다 :

f(n) ≠ O(g(n)) 
=> f(n) = w(g(n)) (little-omega note) 
=> g(n) = o(f(n)) (little-o note) 
=> g(n) = O(f(n)) (big-O note) 

결과는 g(n) ≠ O(f(n)) (Big-O note)과 모순된다. 마찬가지로,

g(n) ≠ O(f(n)) 
=> g(n) = w(f(n)) (little-omega note) 
=> f(n) = o(g(n)) (little-o note) 
=> f(n) = O(g(n)) (big-O note) 

은 f(n) ≠ O(g(n)) (Big-O note)과 모순됩니다.

이 솔루션은 때때로 사실 말한다 : 내 증거에 잘못했을

For f(n) = 1 and g(n) = ||n*sin(n)|| it is true, 
while for any f(n) = O(g(n)), e.g. f(n) = g(n) = 1, it is not true. 

? 또한, 나는 해결책을 이해할 수 없다. ||n*sin(n)||은 벡터 표준 인과 같습니다.

Answer 1

첫 번째 사실이 아닙니다.이 f(n) ≠ O(g(n))부터 f(n) = w(g(n))을 따르지 않습니다. 이 두 함수는 어떤 점에서 교차하고 그 다음에 다른 점들이 더 커지게됩니다 (간단한 단어를 사용하는 경우). f (n)> f (n) (예 : pi/2)의 ns가 존재하는 경우 n < = 1의 경우 첫 번째 f (n)> g (n) . I는 n*sin(n) 생각

Answer 2

은 심지어 큰 O & 따라서 f(n) ≠ O(g(n)) and g(n) ≠ O(f(n))

을 정의하기 위해 사용되는 상수 승산기 모든 선택에 대한 N의 연속 값 & 미만 f(n) = 1 커지고 유지 함수임을 보여준다 g(n) = 2*sin(n)과 같은 순전 한 함수는 여기서는 좋지 않습니다. 이것은 f(n) = 1을 번갈아 계속 유지한다고 생각할 수도 있지만 g(n) = O(f(n)) : M*f(n) > g(n) for M = 3 등