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()rem1618 said:Ah right. I had thought 100000 was small because I've read that Python can represent numbers up to around 10^308, but that was for floats. When I changed fib(n) to calculate with floats instead the runtime did indeed turn linear.
rem1618 said:I've read that Python can represent numbers up to around 10^308
mfb said:10^308 has just ~1000 binary digits. The 100000. fibonacci number is way larger than that.
Floats can be added in constant time, but you lose the precision for large numbers.
In computer science, "O(n^2)" is used to represent the worst-case time complexity of an algorithm, where "n" represents the size of the input. This means that as the input size increases, the time it takes for the algorithm to run will increase at a quadratic rate.
The complexity of a code can be determined by analyzing the number of iterations or operations performed on the input size. In general, loops and nested loops will result in O(n^2) complexity, as the number of operations increases exponentially with the input size.
O(n^2) complexity is considered bad because it can significantly slow down the performance of the code, especially for large input sizes. This can make the code inefficient and impractical for real-world use.
Some common examples of code with O(n^2) complexity are nested for loops, bubble sort, and selection sort. In these cases, the number of operations increases exponentially with the input size, resulting in a quadratic time complexity.
To improve the complexity of your code from O(n^2), you can try to optimize your algorithms and data structures. For example, using divide and conquer techniques or implementing more efficient sorting algorithms like merge sort or quicksort can reduce the time complexity to O(nlogn). It is also important to carefully analyze and design your code to avoid unnecessary loops and operations.