3 ms·

I remember from college there was big-Oh `O(x)` and little-Oh `o(x)`. Is Omega/Theta the same as little-Oh?

• tsimionescu 4y ago
  No, big O is a kind of loose upper bound, while little-O is a very strict upper bound. f(x) = O(g(x)) <=> there exists k, x0 such that f(x) < k * g(x) for any x > x0 f(x) = o(g(x)) <=> for any k > 0, there exists x0 s.t. f(x) < k * g(x) for any x > x0 For example: f(n) = 3*n^2 + 2n + 1 f(n) = O(n^2)? let's take k = 10 3*n^2 + 2n + 1 < 2 * n^2 for any n > n0? n = 0: 3 * 0^2 + 2*0 + 1 < 10 * 0^2 <=> 1 < 0 false n = 1: 3 * 1^2 + 2*1 + 1 < 10 * 1^2 <=> 6 < 10 true n = 2: 3 * 2^2 + 2*2 + 1 < 10 * 2^2 <=> 17 < 40 true ... so, yes, f(n) = O(n^2) (n0 = 1) f(n) = o(n^2) ? let's take k = 2. 3*n^2 + 2n + 1 < 2 * n^2 for any n > n0? 3 * n^2 + 2 * n + 1 < 2 * n^2 <=> 3 * n^2 + 2 * n + 1 - 2 * n^2 < 0 <=> n^2 + 2 * n + 1 < 0 false for any n > 0. so no, f(n) != o(n^2). However, f(n) = o(10 * n^2), and f(n) = o(n^3). Big-Omega and small-Omega are the same idea for a lower bound. Big-Theta is a tight bound around the function: f(n) = Theta(g(n)) <=> there exists k1, k2, n0 such that k1*g(n) < f(n) < k2*g(n), for any n > n0. There is no equivalent "little-theta", as that would imply that the relation must hold for any k1 and k2, which would at best leave only the function itself as fulfilling the condition.