Big-Ω (Big-Omega) notation

Sometimes, we want to say that an algorithm takes at least a certain amount of time, without providing an upper bound. We use big-Ω notation; that's the Greek letter "omega."

If a running time is Ω(f(n))\Omega(f(n)), then for large enough nn, the running time is at least kf(n)k⋅f(n) for some constant kk. Here's how to think of a running time that is Ω(f(n))\Omega(f(n)):

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy