0
$\begingroup$

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 Ω?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ I think it is too broad. Roughly speaking, its highest term is also the lower bound of the function in the sense of $\Omega$. $\endgroup$ – xskxzr Mar 26 '18 at 12:12
  • 1
    $\begingroup$ For every function $f(n)$ it holds that $f(n) = \Omega(f(n))$, and this is a tight lower bound. $\endgroup$ – Yuval Filmus Mar 26 '18 at 12:17
  • $\begingroup$ 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. $\endgroup$ – Vagabond Mar 26 '18 at 12:18
  • $\begingroup$ The highest order term is not only big O but also big $\Omega$ (and big $\Theta$). $\endgroup$ – Yuval Filmus Mar 26 '18 at 12:19
  • $\begingroup$ 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... $\endgroup$ – Vagabond Mar 26 '18 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.