Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #4336 > unrolled thread
| Started by | lalit <opposite800@gmail.com> |
|---|---|
| First post | 2011-04-29 20:22 -0700 |
| Last post | 2011-05-02 23:46 -0600 |
| Articles | 3 on this page of 43 — 15 participants |
Back to article view | Back to comp.lang.python
Fibonacci series recursion error lalit <opposite800@gmail.com> - 2011-04-29 20:22 -0700
Re: Fibonacci series recursion error Gary Herron <gherron@islandtraining.com> - 2011-04-29 20:41 -0700
Re: Fibonacci series recursion error Jason Friedman <jason@powerpull.net> - 2011-04-30 03:57 +0000
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-29 23:45 -0500
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-29 23:51 -0500
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-30 00:31 -0500
Re: Fibonacci series recursion error Peter Otten <__peter__@web.de> - 2011-04-30 08:14 +0200
Re: Fibonacci series recursion error rusi <rustompmody@gmail.com> - 2011-05-02 00:08 -0700
Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-04-30 06:50 +0100
Re: Fibonacci series recursion error Paul Rudin <paul.nospam@rudin.co.uk> - 2011-04-30 06:43 +0100
Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-04-29 23:27 -0600
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-30 00:35 -0500
Re: Fibonacci series recursion error Peter Otten <__peter__@web.de> - 2011-04-30 08:32 +0200
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-04-30 16:37 +1000
Re: Fibonacci series recursion error Thomas Rachel <nutznetz-0c1b6768-bfa9-48d5-a470-7603bd3aa915@spamschutz.glglgl.de> - 2011-04-30 11:37 +0200
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-05-02 16:50 -0500
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 08:17 +1000
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-05-03 12:10 -0500
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-04 07:41 +1000
Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-03 16:31 -0600
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-04 09:09 +1000
Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-02 16:22 -0600
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 08:42 +1000
Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-02 18:48 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 12:13 +1000
Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 15:29 +1000
Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-03 00:52 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Dave Angel <davea@ieee.org> - 2011-05-03 06:32 -0400
Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-03 03:51 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 21:04 +1000
Re: Recursion or iteration (was Fibonacci series recursion error) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-03 12:49 +0000
Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 23:02 +1000
Re: Recursion or iteration (was Fibonacci series recursion error) Hans Mulder <hansmu@xs4all.nl> - 2011-05-12 00:06 +0200
Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-13 04:11 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-13 07:55 -0600
Re: Recursion or iteration (was Fibonacci series recursion error) Hans Mulder <hansmu@xs4all.nl> - 2011-05-13 21:46 +0200
Re: Recursion or iteration (was Fibonacci series recursion error) Mark Dickinson <dickinsm@gmail.com> - 2011-05-13 14:48 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-14 10:24 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-14 15:19 -0600
Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-14 20:32 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Mark Dickinson <dickinsm@gmail.com> - 2011-05-15 12:20 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Mark Dickinson <dickinsm@gmail.com> - 2011-05-15 12:29 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-02 23:46 -0600
Page 3 of 3 — ← Prev page 1 2 [3]
| From | Mark Dickinson <dickinsm@gmail.com> |
|---|---|
| Date | 2011-05-15 12:20 -0700 |
| Subject | Re: Recursion or iteration (was Fibonacci series recursion error) |
| Message-ID | <be75129f-84f4-418e-a0ce-4fb120e1c55f@s14g2000vbi.googlegroups.com> |
| In reply to | #5406 |
On May 15, 4:32 am, rusi <rustompm...@gmail.com> wrote: > On May 15, 2:19 am, Ian Kelly <ian.g.ke...@gmail.com> wrote: > > Yup, linear. Assuming you optimize the even case so that it doesn't > > actually call fib(n//2) twice, the call tree can be approximated as a > > balanced binary tree with height log(n). The total number of nodes in > > the tree is thus O(2 ** log(n)) = O(n). > > It would be linear if the base of the log were 2. > I am not sure it is. > You see the naive fib has a complexity which is fib itself. [Earlier > discussion with Steven] > fib is exponential but with radix < 2 [phi = (1 + sqrt(5))/2 ] > This would suggest that this algo is slightly better than linear. Nope. It's linear, just as Ian Kelly said. If g(n) is the total number of fib calls made for fib(n), then it's easy to show (e.g., by induction) that: (a) g(n) is an increasing function of n, and (b) g(2^k) = 2^k - 1 for all k >= 1. Hence g(n) is O(n). Mark
[toc] | [prev] | [next] | [standalone]
| From | Mark Dickinson <dickinsm@gmail.com> |
|---|---|
| Date | 2011-05-15 12:29 -0700 |
| Subject | Re: Recursion or iteration (was Fibonacci series recursion error) |
| Message-ID | <cf8cc239-01cd-4b6b-8bdd-2d814b2f8e0b@b42g2000yqi.googlegroups.com> |
| In reply to | #5441 |
On May 15, 8:20 pm, Mark Dickinson <dicki...@gmail.com> wrote: > On May 15, 4:32 am, rusi <rustompm...@gmail.com> wrote: > > > On May 15, 2:19 am, Ian Kelly <ian.g.ke...@gmail.com> wrote: > > > Yup, linear. Assuming you optimize the even case so that it doesn't > > > actually call fib(n//2) twice, the call tree can be approximated as a > > > balanced binary tree with height log(n). The total number of nodes in > > > the tree is thus O(2 ** log(n)) = O(n). > > > It would be linear if the base of the log were 2. > > I am not sure it is. > > You see the naive fib has a complexity which is fib itself. [Earlier > > discussion with Steven] > > fib is exponential but with radix < 2 [phi = (1 + sqrt(5))/2 ] > > This would suggest that this algo is slightly better than linear. > > Nope. It's linear, just as Ian Kelly said. If g(n) is the total > number of fib calls made for fib(n), then it's easy to show (e.g., by > induction) that: > > (a) g(n) is an increasing function of n, and > (b) g(2^k) = 2^k - 1 for all k >= 1. > > Hence g(n) is O(n). Hmm. It's even easier: g(n) is: * 1 if n == 1 * n if n > 1, n odd * n-1 if n > 1, n even So definitely linear. :-) -- Mark
[toc] | [prev] | [next] | [standalone]
| From | Ian Kelly <ian.g.kelly@gmail.com> |
|---|---|
| Date | 2011-05-02 23:46 -0600 |
| Subject | Re: Recursion or iteration (was Fibonacci series recursion error) |
| Message-ID | <mailman.1096.1304401650.9059.python-list@python.org> |
| In reply to | #4513 |
On Mon, May 2, 2011 at 11:27 PM, Dan Stromberg <drsalists@gmail.com> wrote:
> But the recursive solution has time complexity of O(logn). The iterative
> solution has time complexity of O(n). That's a significant difference for
> large n - a significant benefit of the recursive version.
It's linear as written. I think you're talking about an
implementation like this one:
def powR(x,n):
if n < 0:
return 1.0 / powR(x, -n)
elif n == 0:
return 1
else:
half_n = n // 2
root = powR(x, half_n)
result = root * root
if half_n + half_n == n - 1:
result = result * x
return result
That's O(log n), but it was harder to write, and it could just as
easily be iterative. In fact it might actually have been a bit
simpler to write it iteratively.
[toc] | [prev] | [standalone]
Page 3 of 3 — ← Prev page 1 2 [3]
Back to top | Article view | comp.lang.python
csiph-web