Computing Big O for a given function/ Figuring out the more relevant term of a function

Question

Considering we have a function:
$$ f_{n, m} : \mathbb{N ^ 2} \rightarrow [0, 1]\\ \{n, m\} \in \mathbb{N ^ 2}\\ f_{n, m}(x, t) = {m \choose x} \cdot \prod_{j=0}^{x-1} \dfrac{t-j}{n-j} $$ We want to find find out which of the two terms($x$ and $t$) affect the value of $f$ more.
I believe we can figure this out if we compute $O(f)$, though I might be wrong.

My guess is that $t$ affects the function value more than $x$ does.
How can I be sure? Should I compute $O(f)$? If yes, how? Which other ways are there?

Which is it, $f_{n, m}$ or $f(x, t)$? What is $m, n$ in the second case? Their values are critical here. — vonbrand, Apr 10 '20 at 00:36
if $x > m$, the binomial coefficient is zero. Thus only $t$ is relevant, and you get $O(t^x)$ if $x \le m$. — vonbrand, Apr 10 '20 at 02:19

score 0 · Accepted Answer · answered Apr 10 '20 at 02:27

We better have $n \gt j-1$ or you get a zero in the denominator. Let us assume $t$ is a natural number. We can then write $f$ in terms of factorials. If $t \gt x-1$ as well (otherwise the function is zero) $$f_{n,m}(x,t)=\frac {m!}{x!(m-x)!}\cdot \frac{t!(n-x)!}{n!(t-x)!}$$ Now it looks like $t$ will be more important because it is the larger factorial and there are terms going both ways in $x$.

Computing Big O for a given function/ Figuring out the more relevant term of a function

1 Answers1