Google Interview Hacks

What is the formal definition of Little-Oh notation? Answer: T(n) = o(f(n)) if and only if for all constants c > 0, ∃ a constant n₀ such that T(n) ≤ c × f(n) ∀n ≥ n₀.

What is the formal definition of Theta notation? Answer: T(n) = θ(f(n)) if and only if T(n) = O(f(n)) and T(n) = Omega(f(n)). ∃ constants c₁, c₂, n₀ such that c₁ × f(n) ≤ T(n) ≤ c₂ × f(n) for all n ≥ n₀.

What is the formal definition of Omega notation? Answer: T(n) = Omega(f(n)) if and only if ∃ constants c, n₀ such that T(n) ≥ c × f(n) ∀n ≥ n₀.

What is the formal definition of Big-Oh notation? T(n) = O(f(n)) if and only if there exist constants c, n₀ > 0 such that T(n) ≤ c × f(n) for all n ≥ n₀. n₀ is the crossing point. c, n₀ must be independent of n.

What is the high-level idea about asymptotic analysis? Asymptotic analysis suppresses constant factors and lower-order terms.