0

Suppose we are given a rational function $f(n)=\frac{p(n)}{q(n)}$ and need to find g(n) that satisfies: $f(n) \in \Theta(g(n))$. Does g(n) need to be one of $n^c, log n, n log n$ or can it be, in this case $g(n)=f(n)=\frac{p(n)}{q(n)}?$

EggHead
  • 667

2 Answers2

1

Certainly if $g(n)=f(n)$ you have $f(n) \in \Theta(g(n))$ It is true, but often it will miss the point. The idea is to have $g(n)$ look like one of the things you cite to get an idea how it compares to other problems.

Ross Millikan
  • 374,822
1

Of course $f(n) \in \Theta(f(n))$ by definition of $\Theta$, but usually what the question is asking for is a simple function $g$. In this case you would only need the most significant term from the top and the bottom each. The proof of that goes like this:

For any $p(n) = a(n)+b(n)$ and $q(n) = c(n) + d(n)$ where $b(n) \in o(a(n))$ and $d(n) \in o(c(n))$ and $a(n) \ne 0$ and $c(n) \ne 0$,

  $\frac{p(n)}{q(n)} = \frac{a(n)}{c(n)} (1+\frac{b(n)}{a(n)}) (1+\frac{d(n)}{c(n)})^{-1} \in \frac{a(n)}{c(n)} (1+\frac{b(n)}{a(n)}) (1-O(\frac{d(n)}{c(n)}))$

  $\in \frac{a(n)}{c(n)} (1+o(1)) (1+o(1)) = \frac{a(n)}{c(n)} (1+o(1)) = \Theta(\frac{a(n)}{c(n)})$

user21820
  • 57,693
  • 9
  • 98
  • 256
  • The method you outlined works when $p(n)$ is of higher degree than $q(n)$, in which case $g(n)$ is of the form $n^c$. However, when the converse is true, $g(n)$ is of the form $\frac{1}{n^c}$ which would mean $f(n) \in \Theta(\frac{1}{n^c})$ which is counter intuitive since it would mean that efficiency gets better as input size increases. Does the method you outlined work in this case? Thanks! – EggHead Jan 26 '14 at 14:24
  • The proof works for any functions that satisfy the conditions I gave, including non-polynomials. The definition of $\Theta$ only requires the ratio tending to a non-zero constant, and so although algorithms never have complexity less than $\Theta(n)$ if $n$ is the input size, it is not contradictory. For example as $x \to \infty$, $\frac{1}{x}-\frac{1}{x+1} = \frac{1}{x^2+x} \in \Theta(\frac{1}{x^2})$. Also, $\frac{1}{x}-\frac{1}{x+1} = \frac{1}{x^2} - \frac{1}{x^3+x^2} \in \frac{1}{x^2} + \Theta(\frac{1}{x^3})$. You can get a free graphing software from http://www.padowan.dk/ to plot these. – user21820 Jan 27 '14 at 02:02
  • Thanks. I already have graphing software and I used it to verify that my choice of g(n) did bound f(n). – EggHead Jan 27 '14 at 03:57