- #1

- 14

- 0

f0, f1, = 0, 1

for i in range(n - 1):

f0, f1 = f1, f0 + f1

return f1

It looks like it'd be linear, given there's only one loop, but when I plotted n against runtime, the relationship was quadratic, why?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter rem1618
- Start date

- #1

- 14

- 0

f0, f1, = 0, 1

for i in range(n - 1):

f0, f1 = f1, f0 + f1

return f1

It looks like it'd be linear, given there's only one loop, but when I plotted n against runtime, the relationship was quadratic, why?

- #2

mfb

Mentor

- 35,356

- 11,680

Does your addition happen in constant time, independent of the size of the numbers?

- #3

- 14

- 0

- #4

jim mcnamara

Mentor

- 4,284

- 2,886

- #5

mfb

Mentor

- 35,356

- 11,680

@rem1618: What is the range of n you tested?

- #6

- 14

- 0

They're not huge numbers, I ran it in range(0, 100000, 10000). This was the plot I got

The rest of my code is just for clocking runtime and plotting, so there should be nothing special there, but here it is.

The rest of my code is just for clocking runtime and plotting, so there should be nothing special there, but here it is.

Code:

```
import time
from pylab import *
def fib(n):
....f0, f1, = 0, 1
....for i in xrange(n - 1):
........f0, f1 = f1, f0 + f1
....return f1
limits = (0, 100000, 10000)
n_N = range(*limits)
n_t = []
n2_N = [i**2 for i in n_N]
for i in n_N:
....start = time.clock()
....fib(i)
....end = time.clock()
....diff = end - start
....n_t.append(diff)
figure()
subplot(211)
title('Complexity of Iterative Fib')
xlabel('n')
ylabel('runtime (s)')
plot(n_N, n_t)
subplot(212)
title('Complexity of n^2')
xlabel('n')
ylabel('runtime (s)')
plot(n_N, n2_N)
show()
```

Last edited by a moderator:

- #7

mfb

Mentor

- 35,356

- 11,680

- #8

AlephZero

Science Advisor

Homework Helper

- 6,994

- 293

Take home lesson from this: the downside of an "ultra-user-friendly" language like Python is that many users don't know what's their programs are actually doing, so long as they "seem to work OK".

And statements like "from pylab import *" don't make it any easier to find out what's going on!

- #9

- 14

- 0

- #10

mfb

Mentor

- 35,356

- 11,680

Floats can be added in constant time, but you lose the precision for large numbers.

- #11

- 297

- 2

Sure, but keep in mind that floats can still only represent a certain number of digits, and some numbers can't be represented exactly at all. Floating point is imprecise. I bet your answers are essentially wrong past a certain number of digits in the answer. Make sure you understand how floating point numbers work before using them. They do have pitfalls.

Might want to read the wiki page on them: http://en.wikipedia.org/wiki/Floating_point

- #12

Borek

Mentor

- 28,660

- 3,153

I've read that Python can represent numbers up to around 10^308

That's just 64-bit float (double precision float, IEEE 754), standard format on Intel processors (and others). Nothing specifically pythonesque about it.

- #13

- 14

- 0

Floats can be added in constant time, but you lose the precision for large numbers.

You're totally right. I don't know what my mind was thinking haha. And yes, I'm aware of the precision issue with floats. I was mostly just experimenting with the runtime, because I've only recently realized the iterative algorithm is way faster than the recursive one for fibonacci numbers.

Share: