Skip to main content
edited title
Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Asymptotic notation between two setsets of variables

added 4 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

I have problems interpreting the definition of asymptotic notation where the functions involve two different set of variables. I am quite confident with the definition of $f(n) = O(g(n))$ and its extension to the multivariable case ($f(n, m) = O(g(n, m))$). However I don't acutallyactually understand the meaning of $f(n) = O(g(m))$ since $f$ and $g$ work with two different variables.

If for exameexample I have that $n = O(m)$, the intuition behind this is that $m$ upper bounds $n$ but I'm not quite sure how to apply the formal definition of big O. The first idea was to use a dummy function approach by defining $f(n, m) = n$ and $g(n, m) = m$ but this does not work out well.

Another idea was to assume that both $n$ and $m$ are a function of some unkownunknown variables that dependsdepend on the problem at hand. In this case $n = n(x_1, \ldots, x_k)$, $m = m(x_1, \ldots, x_k)$ and $n(x_1, \ldots, x_k) = O(m(x_1, \ldots, x_k))$.

Is this right? Am I missing something?

I have problems interpreting the definition of asymptotic notation where the functions involve two different set of variables. I am quite confident with the definition of $f(n) = O(g(n))$ and its extension to the multivariable case ($f(n, m) = O(g(n, m))$). However I don't acutally understand the meaning of $f(n) = O(g(m))$ since $f$ and $g$ work with two different variables.

If for exame I have that $n = O(m)$, the intuition behind this is that $m$ upper bounds $n$ but I'm not quite sure how to apply the formal definition of big O. The first idea was to use a dummy function approach by defining $f(n, m) = n$ and $g(n, m) = m$ but this does not work out well.

Another idea was to assume that both $n$ and $m$ are function of some unkown variables that depends on the problem at hand. In this case $n = n(x_1, \ldots, x_k)$, $m = m(x_1, \ldots, x_k)$ and $n(x_1, \ldots, x_k) = O(m(x_1, \ldots, x_k))$.

Is this right? Am I missing something?

I have problems interpreting the definition of asymptotic notation where the functions involve two different set of variables. I am quite confident with the definition of $f(n) = O(g(n))$ and its extension to the multivariable case ($f(n, m) = O(g(n, m))$). However I don't actually understand the meaning of $f(n) = O(g(m))$ since $f$ and $g$ work with two different variables.

If for example I have that $n = O(m)$, the intuition behind this is that $m$ upper bounds $n$ but I'm not quite sure how to apply the formal definition of big O. The first idea was to use a dummy function approach by defining $f(n, m) = n$ and $g(n, m) = m$ but this does not work out well.

Another idea was to assume that both $n$ and $m$ are a function of some unknown variables that depend on the problem at hand. In this case $n = n(x_1, \ldots, x_k)$, $m = m(x_1, \ldots, x_k)$ and $n(x_1, \ldots, x_k) = O(m(x_1, \ldots, x_k))$.

Is this right? Am I missing something?

Source Link

Asymptotic notation between two set of variables

I have problems interpreting the definition of asymptotic notation where the functions involve two different set of variables. I am quite confident with the definition of $f(n) = O(g(n))$ and its extension to the multivariable case ($f(n, m) = O(g(n, m))$). However I don't acutally understand the meaning of $f(n) = O(g(m))$ since $f$ and $g$ work with two different variables.

If for exame I have that $n = O(m)$, the intuition behind this is that $m$ upper bounds $n$ but I'm not quite sure how to apply the formal definition of big O. The first idea was to use a dummy function approach by defining $f(n, m) = n$ and $g(n, m) = m$ but this does not work out well.

Another idea was to assume that both $n$ and $m$ are function of some unkown variables that depends on the problem at hand. In this case $n = n(x_1, \ldots, x_k)$, $m = m(x_1, \ldots, x_k)$ and $n(x_1, \ldots, x_k) = O(m(x_1, \ldots, x_k))$.

Is this right? Am I missing something?