ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 17 Mar 2013 17:14:09 -0500Empirical 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 02:07:41 -0500https://ask.sagemath.org/question/9914/empirical-data-plot/Comment 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 04:33:38 -0500https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18061#post-id-18061Comment 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 02:47:00 -0500https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18064#post-id-18064Comment 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 02:47:27 -0500https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18063#post-id-18063Comment 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 04:28:19 -0500https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18062#post-id-18062Answer 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 06:06:19 -0500https://ask.sagemath.org/question/9914/empirical-data-plot/?answer=14654#post-id-14654Comment 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 06:54:01 -0500https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18056#post-id-18056Comment 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 06:45:47 -0500https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18060#post-id-18060Comment 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 12:36:18 -0500https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18058#post-id-18058Comment 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 17:14:09 -0500https://ask.sagemath.org/question/9914/empirical-data-plot/?comment=18053#post-id-18053