JamCoders

💾 Download

Day 4, Session 1

Time Complexity

import time

We noticed in fib exercise that some functions take longer than others -- even our computer isn't fast enough to do every function "instantly"

def fib_i(n):

    prev_prev = 0  # initialized to F(0)
    prev = 1       # initialized to F(1)
    
    for i in range(n - 1):
        # compute the next number in the sequence
        fib_i = prev_prev + prev
        # save state to use for the next computation
        prev_prev = prev
        prev = fib_i
        
    return fib_i

fib_i(35)

9227465

def fib_r(n):
    if n == 0 or n == 1: 
        return n
    else: 
        return fib_r(n-1) + fib_r(n-2)

fib_r(35)

9227465

start = time.time()
fib_i(36)
end = time.time()
print(end - start)

0.0

start = time.time()
fib_r(36)
end = time.time()
print(end - start)

65.96614527702332

We can experiment with how long a function takes with a simple example

for i in range(100000000):
    result = i
print(result)

99999999

start = time.time()

n = 10**7
for i in range(n):
    result = i
    
end = time.time()

time_1 = end - start
print('n:', n, 'time:', time_1, 'seconds')

n: 10000000 time: 0.7320683002471924 seconds

start = time.time()

n = 2*10**7
for i in range(n):
    result = i
    
end = time.time()

time_2 = end - start
print('n:', n, 'time:', time_2, 'seconds')

n: 20000000 time: 1.4678118228912354 seconds

start = time.time()

n = 3*(10**7)
for i in range(n):
    result = i
    
end = time.time()

time_3 = end - start
print('n: ', n, 'time: ', time_3, 'seconds')

n:  30000000 time:  2.33735990524292 seconds

start = time.time()

n = 4*(10**7)
for i in range(n):
    result = i
    
end = time.time()

time_4 = end - start
print('n:', n, 'time: ', time_4, 'seconds')

n: 40000000 time:  3.0218048095703125 seconds

start = time.time()

n = 5*(10**7)
for i in range(n):
    result = i
    
end = time.time()

time_5 = end - start
print('n:', n, 'time:', time_5, 'seconds')

n: 50000000 time: 3.6232779026031494 seconds

from matplotlib import pyplot as plt

plt.scatter([1*(10**7),2*(10**7),3*(10**7),4*(10**7),5*(10**7)], [time_1,time_2,time_3,time_4,time_5])
plt.title('Time vs n')
plt.xlabel('n')
plt.ylabel('Time (s)')
plt.show()

start = time.time()
n = 10000
for i in range(n):
    for j in range(n):
        result = j
print(result)
end = time.time()
print(end - start,'seconds')

9999
10.06101369857788 seconds

start = time.time()

for i in range(1000):
    for j in range(1000):
        result = j
    
end = time.time()

time_1 = end-start
print('n:', 1000, 'time:', time_1, 'seconds')

n: 1000 time: 0.11469531059265137 seconds

start = time.time()

for i in range(2000):
    for j in range(2000):
        result = j
    
end = time.time()

time_2 = end-start
print('n:', 2000, 'time:', time_2, 'seconds')

n: 2000 time: 0.319150447845459 seconds

start = time.time()

for i in range(3000):
    for j in range(3000):
        result = j
    
end = time.time()

time_3 = end-start
print('n:', 3000, 'time:', time_3, 'seconds')

n: 3000 time: 0.7676026821136475 seconds

start = time.time()

for i in range(4000):
    for j in range(4000):
        result = j
    
end = time.time()

time_4 = end-start
print('n:', 4000, 'time:', time_4, 'seconds')

n: 4000 time: 1.2762105464935303 seconds

start = time.time()

for i in range(5000):
    for j in range(5000):
        result = j
    
end = time.time()

time_5 = end-start
print('n:', 5000, 'time:', time_5, 'seconds')

n: 5000 time: 2.57820987701416 seconds

start = time.time()

for i in range(6000):
    for j in range(6000):
        result = j
    
end = time.time()

time_6 = end-start
print('n:', 6000, 'time:', time_6, 'seconds')

n: 6000 time: 2.983295202255249 seconds

start = time.time()

for i in range(7000):
    for j in range(7000):
        result = j
    
end = time.time()

time_7 = end-start
print('n:', 7000, 'time:', time_7, 'seconds')

n: 7000 time: 4.916358709335327 seconds

start = time.time()

for i in range(8000):
    for j in range(8000):
        result = j
    
end = time.time()

time_8 = end-start
print('n:', 7000, 'time:', time_8, 'seconds')

n: 7000 time: 6.585402965545654 seconds

plt.scatter([1000,2000,3000,4000,5000,6000,7000,8000], [time_1,time_2,time_3,time_4,time_5,time_6,time_7,time_8])
plt.title('Time vs Iterations')
plt.xlabel('Iterations')
plt.ylabel('Time (s)')
plt.show()