ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 17 Mar 2013 23:14:09 +0100Empirical Data Plothttps://ask.sagemath.org/question/9914/empirical-data-plot/I wish to make a plot of N vs Time where $N=$ # of edges in a graph.
i.e. i want to make an empirical estimate of the time complexity it takes to compute certain things about a graph based on its number of edges.
so i guess i'm wanting to know how i can plot these data points in sage and find a polynomial that best fits?
i.e.
N = [(16,28,59,120)]
T = [(0.135,0.523,7.36,248)] --where time is measured in seconds
i'm a beginner so any help will be much appreciated.Fri, 15 Mar 2013 08:07:41 +0100https://ask.sagemath.org/question/9914/empirical-data-plot/Comment by jtaa for <p>I wish to make a plot of N vs Time where $N=$ # of edges in a graph.
i.e. i want to make an empirical estimate of the time complexity it takes to compute certain things about a graph based on its number of edges.</p>
<p>so i guess i'm wanting to know how i can plot these data points in sage and find a polynomial that best fits?</p>
<p>i.e. <br/>
N = [(16,28,59,120)] <br/>
T = [(0.135,0.523,7.36,248)] --where time is measured in seconds </p>
<p>i'm a beginner so any help will be much appreciated.</p>
https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18062#post-id-18062well, i just want to know the order of growth. i.e. as the edges increase what is the order of growth in terms of time taken to compute my function.Fri, 15 Mar 2013 10:28:19 +0100https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18062#post-id-18062Comment by kcrisman for <p>I wish to make a plot of N vs Time where $N=$ # of edges in a graph.
i.e. i want to make an empirical estimate of the time complexity it takes to compute certain things about a graph based on its number of edges.</p>
<p>so i guess i'm wanting to know how i can plot these data points in sage and find a polynomial that best fits?</p>
<p>i.e. <br/>
N = [(16,28,59,120)] <br/>
T = [(0.135,0.523,7.36,248)] --where time is measured in seconds </p>
<p>i'm a beginner so any help will be much appreciated.</p>
https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18063#post-id-18063That said, you could certainly try fitting to various things like `x^2` or `x log(x)` with `find_fit`, see http://www.sagemath.org/doc/reference/sage/numerical/optimize.html#sage.numerical.optimize.find_fitFri, 15 Mar 2013 08:47:27 +0100https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18063#post-id-18063Comment by kcrisman for <p>I wish to make a plot of N vs Time where $N=$ # of edges in a graph.
i.e. i want to make an empirical estimate of the time complexity it takes to compute certain things about a graph based on its number of edges.</p>
<p>so i guess i'm wanting to know how i can plot these data points in sage and find a polynomial that best fits?</p>
<p>i.e. <br/>
N = [(16,28,59,120)] <br/>
T = [(0.135,0.523,7.36,248)] --where time is measured in seconds </p>
<p>i'm a beginner so any help will be much appreciated.</p>
https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18064#post-id-18064It's highly unlikely that you'll want a polynomial that gives best fit; you can get a polynomial with a PERFECT fit if you choose a high enough degree polynomial! You may want to look at general books on data analysis.Fri, 15 Mar 2013 08:47:00 +0100https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18064#post-id-18064Comment by ppurka for <p>I wish to make a plot of N vs Time where $N=$ # of edges in a graph.
i.e. i want to make an empirical estimate of the time complexity it takes to compute certain things about a graph based on its number of edges.</p>
<p>so i guess i'm wanting to know how i can plot these data points in sage and find a polynomial that best fits?</p>
<p>i.e. <br/>
N = [(16,28,59,120)] <br/>
T = [(0.135,0.523,7.36,248)] --where time is measured in seconds </p>
<p>i'm a beginner so any help will be much appreciated.</p>
https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18061#post-id-18061@kcrisman is right. You can always have a polynomial of degree at most len(N)-1 that perfectly fits the solution. Finding such a polynomial would require the same time as inverting a (len(N)-1) x (len(N)-1) matrix.
There possibly exists a more "straightforward" (but complex) expression too since the inverse of a Vandermond matrix is known.Fri, 15 Mar 2013 10:33:38 +0100https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18061#post-id-18061Answer by kcrisman for <p>I wish to make a plot of N vs Time where $N=$ # of edges in a graph.
i.e. i want to make an empirical estimate of the time complexity it takes to compute certain things about a graph based on its number of edges.</p>
<p>so i guess i'm wanting to know how i can plot these data points in sage and find a polynomial that best fits?</p>
<p>i.e. <br/>
N = [(16,28,59,120)] <br/>
T = [(0.135,0.523,7.36,248)] --where time is measured in seconds </p>
<p>i'm a beginner so any help will be much appreciated.</p>
https://ask.sagemath.org/question/9914/empirical-data-plot/?answer=14654#post-id-14654Here is a sample of what you can do in Sage.
var('a,n')
model(x) = a*x^n
N = [16,28,59,120]
T = [0.135,0.523,7.36,248]
data = zip(N,T)
@interact
def _(n=[1..5]):
L = find_fit(data,model.subs(n=n))
show(plot(model.subs(a=L[0].rhs(),n=n),(x,0,120))+points(data,pointsize=20,color='black'))
See it [live and in action here](http://sagecell.sagemath.org/?z=eJxNjs2OwjAMhO95itxqgxWlLQV2pUg8AOLErSoo9EdE202qJkDF05PCBZ9Gns-euesREk02QfbvmraHCbniejGdLDtEVaZryrZU_FCayYqz47yTIs0LkqLIctqIPBKrbcUaHXR0n2aAAx2R7YwN7ajrwJq242ewqkyFKCr8ZTzOPrKdsc25MwHmW3oXEP528ZG1iG_MX90Dht4F-LK12peyEuPVA9LMEkwk54qIy8HFYP95-dHm2apMUu16N6rk0uv6L0F8AYivSF0=&lang=sage). Note that with four data points, of course the fifth-degree one is perfect! My guess is that here you may have (yuck) exponential growth, but without more data it's hard to be sure - definitely could also be $O(x^3)$ or $O(x^4)$ or something.Fri, 15 Mar 2013 12:06:19 +0100https://ask.sagemath.org/question/9914/empirical-data-plot/?answer=14654#post-id-14654Comment by jtaa for <p>Here is a sample of what you can do in Sage.</p>
<pre><code>var('a,n')
model(x) = a*x^n
N = [16,28,59,120]
T = [0.135,0.523,7.36,248]
data = zip(N,T)
@interact
def _(n=[1..5]):
L = find_fit(data,model.subs(n=n))
show(plot(model.subs(a=L[0].rhs(),n=n),(x,0,120))+points(data,pointsize=20,color='black'))
</code></pre>
<p>See it <a href="http://sagecell.sagemath.org/?z=eJxNjs2OwjAMhO95itxqgxWlLQV2pUg8AOLErSoo9EdE202qJkDF05PCBZ9Gns-euesREk02QfbvmraHCbniejGdLDtEVaZryrZU_FCayYqz47yTIs0LkqLIctqIPBKrbcUaHXR0n2aAAx2R7YwN7ajrwJq242ewqkyFKCr8ZTzOPrKdsc25MwHmW3oXEP528ZG1iG_MX90Dht4F-LK12peyEuPVA9LMEkwk54qIy8HFYP95-dHm2apMUu16N6rk0uv6L0F8AYivSF0=&lang=sage">live and in action here</a>. Note that with four data points, of course the fifth-degree one is perfect! My guess is that here you may have (yuck) exponential growth, but without more data it's hard to be sure - definitely could also be $O(x^3)$ or $O(x^4)$ or something.</p>
https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18053#post-id-18053awesome thanksSun, 17 Mar 2013 23:14:09 +0100https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18053#post-id-18053Comment by jtaa for <p>Here is a sample of what you can do in Sage.</p>
<pre><code>var('a,n')
model(x) = a*x^n
N = [16,28,59,120]
T = [0.135,0.523,7.36,248]
data = zip(N,T)
@interact
def _(n=[1..5]):
L = find_fit(data,model.subs(n=n))
show(plot(model.subs(a=L[0].rhs(),n=n),(x,0,120))+points(data,pointsize=20,color='black'))
</code></pre>
<p>See it <a href="http://sagecell.sagemath.org/?z=eJxNjs2OwjAMhO95itxqgxWlLQV2pUg8AOLErSoo9EdE202qJkDF05PCBZ9Gns-euesREk02QfbvmraHCbniejGdLDtEVaZryrZU_FCayYqz47yTIs0LkqLIctqIPBKrbcUaHXR0n2aAAx2R7YwN7ajrwJq242ewqkyFKCr8ZTzOPrKdsc25MwHmW3oXEP528ZG1iG_MX90Dht4F-LK12peyEuPVA9LMEkwk54qIy8HFYP95-dHm2apMUu16N6rk0uv6L0F8AYivSF0=&lang=sage">live and in action here</a>. Note that with four data points, of course the fifth-degree one is perfect! My guess is that here you may have (yuck) exponential growth, but without more data it's hard to be sure - definitely could also be $O(x^3)$ or $O(x^4)$ or something.</p>
https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18058#post-id-18058Time = [0.135, 0.523, 2.72, 7.36, 23.2, 45.1, 96.3, 248]
Edges = [16.0, 28.0, 47.0, 59.0, 77.0, 84.0, 98.0, 120.0] -- seems like it's more like O(N^5) growth with these additional points?Fri, 15 Mar 2013 18:36:18 +0100https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18058#post-id-18058Comment by ppurka for <p>Here is a sample of what you can do in Sage.</p>
<pre><code>var('a,n')
model(x) = a*x^n
N = [16,28,59,120]
T = [0.135,0.523,7.36,248]
data = zip(N,T)
@interact
def _(n=[1..5]):
L = find_fit(data,model.subs(n=n))
show(plot(model.subs(a=L[0].rhs(),n=n),(x,0,120))+points(data,pointsize=20,color='black'))
</code></pre>
<p>See it <a href="http://sagecell.sagemath.org/?z=eJxNjs2OwjAMhO95itxqgxWlLQV2pUg8AOLErSoo9EdE202qJkDF05PCBZ9Gns-euesREk02QfbvmraHCbniejGdLDtEVaZryrZU_FCayYqz47yTIs0LkqLIctqIPBKrbcUaHXR0n2aAAx2R7YwN7ajrwJq242ewqkyFKCr8ZTzOPrKdsc25MwHmW3oXEP528ZG1iG_MX90Dht4F-LK12peyEuPVA9LMEkwk54qIy8HFYP95-dHm2apMUu16N6rk0uv6L0F8AYivSF0=&lang=sage">live and in action here</a>. Note that with four data points, of course the fifth-degree one is perfect! My guess is that here you may have (yuck) exponential growth, but without more data it's hard to be sure - definitely could also be $O(x^3)$ or $O(x^4)$ or something.</p>
https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18060#post-id-18060Actually, a degree 3 polynomial is sufficient to fit the data. See [this interact](http://sagecell.sagemath.org/?z=eJxlkD9PwzAQxfd8iluq3IEV5U8DpVIkmFiiDtCtCshNbGrFjSM7haiI746TbHCLn3zv_c6-HRRwSO5YumH5A0vSuAr201UcJVnO4ihPM3YfZd6w3lRBwwfuu1fV447tKQgeVTcIy-shaIQEKbEt1rQNwNf4ya3zZn_gIRxXTbhCRSCNBQWqA8u7D4EtVTTbz6YRGkfyCXc545w-qApuYHxT_1NLqPRuqbrmXaoBp8exhbN0n16eX73hu_ScSJ8c0hZmbSf9l6lFhyXRD8xZdzJf2Gsz4AyM3OXocAISw5HF06aIbnvj_--WyYtWV1GkMauNNrYIj5rXbUj0C89DZ5Y=&lang=sage).
The complexity is polynomial in the number of data points.Fri, 15 Mar 2013 12:45:47 +0100https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18060#post-id-18060Comment by kcrisman for <p>Here is a sample of what you can do in Sage.</p>
<pre><code>var('a,n')
model(x) = a*x^n
N = [16,28,59,120]
T = [0.135,0.523,7.36,248]
data = zip(N,T)
@interact
def _(n=[1..5]):
L = find_fit(data,model.subs(n=n))
show(plot(model.subs(a=L[0].rhs(),n=n),(x,0,120))+points(data,pointsize=20,color='black'))
</code></pre>
<p>See it <a href="http://sagecell.sagemath.org/?z=eJxNjs2OwjAMhO95itxqgxWlLQV2pUg8AOLErSoo9EdE202qJkDF05PCBZ9Gns-euesREk02QfbvmraHCbniejGdLDtEVaZryrZU_FCayYqz47yTIs0LkqLIctqIPBKrbcUaHXR0n2aAAx2R7YwN7ajrwJq242ewqkyFKCr8ZTzOPrKdsc25MwHmW3oXEP528ZG1iG_MX90Dht4F-LK12peyEuPVA9LMEkwk54qIy8HFYP95-dHm2apMUu16N6rk0uv6L0F8AYivSF0=&lang=sage">live and in action here</a>. Note that with four data points, of course the fifth-degree one is perfect! My guess is that here you may have (yuck) exponential growth, but without more data it's hard to be sure - definitely could also be $O(x^3)$ or $O(x^4)$ or something.</p>
https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18056#post-id-18056Try [this interact](http://sagecell.sagemath.org/?z=eJxNjs1qwzAQhO96Ct0ktWKR_52CoA8QcsrNuEHxT2KqSsZyW5On78q5dFmGgZlP2h-zcGakY4J8-X6wfBNUU_OyfThyQtckJShJ0zpqXkUtDlGr3dd51MOeJqkC1VJyjpiCJCskVVCkGeJQpYhAVqLPAH1eQIJgCTHN65b0ZjUIPqaZn-RZkPfJrcNiupX0w0gv3OkmBSha8UYozhG74-T6yzitPLJyPx_C9zVg1wmx18Ld__LZ-pX_i40-NqqF5R64kLEr-SaVxPuFeJ09fhyeTz799Bh0qmTnrV80u1rTfTIhQ2fsoJn1N1wm_gCVCliN&lang=sage) with log log scales; that's often more helpful for determining these things. @ppurka - my model intentionally started with zero edges = zero time, so degree three wouldn't suffice.Sat, 16 Mar 2013 12:54:01 +0100https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18056#post-id-18056