# How to find lower bound of f(n) for master theorem

I'm studying the master method to solving a recurrence. It describes three cases, the last one of which depends on what lower bound a function f(n) has.

I usually find out the upper bound of a function from its highest term exponent. How would I figure out its lower bound Ω?

• I think it is too broad. Roughly speaking, its highest term is also the lower bound of the function in the sense of $\Omega$. – xskxzr Mar 26 '18 at 12:12
• For every function $f(n)$ it holds that $f(n) = \Omega(f(n))$, and this is a tight lower bound. – Yuval Filmus Mar 26 '18 at 12:17
• Sorry if it's a broad question. I am learning about asymptotic analysis and don't have a lot of experience. The method asks for the bound but I'm not sure how it is usually found, when applying the method. – Vagabond Mar 26 '18 at 12:18
• The highest order term is not only big O but also big $\Omega$ (and big $\Theta$). – Yuval Filmus Mar 26 '18 at 12:19
• Thanks @YuvalFilmus that's interesting. So if I take a look at the exponent of the higher term that can tell me all of them? The upper and lower bounds are defined by constants c that multiply a function g() that determines the complexity. Is the function always the same and different constants will give us the lower and upper bounds?... Thanks... – Vagabond Mar 26 '18 at 12:22