For any nonnegative functions f(n) and g(n): f(n) is O(g(n)) if and only if g(n) is Ω(f(n))We'll prove this result in two steps:
[Remember that your proof must be general to any functions f(n) and g(n) that are positive. Also, remember to state and use the necessary constants c and n_{0}.]
Solution:
If f(n) is O(g(n)) then
hence:
hence:
which is the definition of g(n) = Ω (f(n)). 
[Remember that your proof must be general to any functions f(n) and g(n) that are positive. Also, remember to state and use the necessary constants c and n_{0}.]
Solution:
If g(n) = Ω (f(n)) then
hence:
hence:
which is the definition of f(n) = O(g(n)). 
function Fibiter(n) { if (n < 2) return n else { temp1 := 0 temp2 := 1 while (n > 1) { sum := temp1 + temp2 temp1 := temp2 temp2 := sum n := n1 } } return sum }
We will concentrate here in T(n) when n ≥ 2 (hence in the proof below, we will use n_{0} ≥ 2):

Solution:
Claim: T(n) = Θ(n).
