2
$\begingroup$

I am running very computationally intensive tasks and wish to adjust the parameters respective of how long it takes.

The function I am running is PLINK - for those who don't know, it is used for genotype data.

The function is said to follow a $O(nm^2)$ w.r.t. big O.

I have the run time for two time points with different parameters for $m$ and a constant $n$, they are: 3 hours and 648 hours.

From this I wish to estimate the run-time for different parameters of $m$, that would respect the $O(nm^2)$ relationship.

Can anybody provide some insight as to methods for estimating run-time with the constant $n$ parameters? In other words, we know for run-time function $R$: $R(n_0, m_1)=3$ and $R(n_0, m_2)=648$, and from this I wish to estimate $R(n_0, m)$ for a general $m$; knowing that it follows a growth function $O(nm^2)$.

$\endgroup$
9
  • 2
    $\begingroup$ If I understand correctly: you have a running-time function $R(n,m)$ whose growth is $O(nm^2)$; you know that for some values $n_0, m_1, m_2$ the outputs are $R(n_0,m_1)=3$ and $R(n_0,m_2)=648$; and you would like to estimate $R(n_0,m)$ for general $m$? $\endgroup$
    – Sambo
    Commented Jul 24, 2019 at 19:19
  • $\begingroup$ @Sambo thanks for your response. That is exactly what I meant, yes. $\endgroup$
    – h3ab74
    Commented Jul 24, 2019 at 19:24
  • $\begingroup$ No problem! You may want to edit your question to clarify it a bit. For writing math on this site, you may want to refer to, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. $\endgroup$
    – Sambo
    Commented Jul 24, 2019 at 19:31
  • 1
    $\begingroup$ Maybe you could make a good enough estimate with just two data points by simplifying your function to e.g. $a_1nm^2 +a_2.$ In this case, you would need to solve a system of equations to determine constants $a_1,a_2.$ Just substitute the values of $n_0,m_1,m_2$ and your running times and solve the system of equations. Then test whether your function gives satisfactory predictions. If not, make it more complex and use more data points. $\endgroup$
    – Tom
    Commented Jul 24, 2019 at 20:24
  • 1
    $\begingroup$ rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation $\endgroup$
    – user645636
    Commented Jul 25, 2019 at 14:39

1 Answer 1

2
$\begingroup$

Okay, if $m^2$ were the only relevant changing value, then I could guess your ratio of $m$ values was roughly, 14.7 (sqrt of 216 roughly) . The notation, is mostly used as a way to show a term or set of terms, that approaches the value of the overall function as it's variable(s) get larger. For example: $$4z^2+ 20876549321768543219865740$$ has a relatively huge constant term. But, by $$z=2284543133854.586647726934526$$ that only accounts for roughly half the value of the polynomial. Above this, the term with a variable, starts to take over half. By :$$z=22845431338545.86647726934526$$ the constant term is now at under 0.1 percent of the value of that function. Above this, a good approximation is simply $$4z^2$$ and above $$z=2$$ this estimate is estimated by $$z^2$$. With $n$ constant, your function if large enough to overwhelm other terms will roughly scale with the square of the ratio of $m$ values.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .