In [1]:
import time
In [2]:
def sum_of_n(n):
    the_sum = 0
    
    for i in range(1, n+1):
        the_sum += i
        
    return the_sum
In [6]:
sum_of_n(10)
Out[6]:
55
In [7]:
sum_of_n(100)
Out[7]:
5050
In [8]:
sum_of_n(1000)
Out[8]:
500500
In [9]:
def foo(tom):
    fred = 0
    for bill in range(1, tom+1):
        barney = bill
        fred = fred + barney
        
    return fred
In [10]:
foo(10)
Out[10]:
55

sum_of_n with timing built in

In [11]:
def sum_of_n_timed(n):
    start = time.time()  # number of seconds since 1/1/1970 UNIX epoch
    
    the_sum = 0
    
    for i in range(1, n+1):
        the_sum += i
        
    end = time.time()
    
    return the_sum, end-start
In [12]:
time.time()
Out[12]:
1593610022.004361
In [84]:
sum_of_n_timed(100)
Out[84]:
(5050, 1.4781951904296875e-05)

$\sum_{i=1}^{n} i = \frac{(n)(n+1)}{2}$

In [15]:
def sum_of_n3_timed(n):
    start = time.time()  # number of seconds since 1/1/1970 UNIX epoch
    
    the_sum = (n * (n+1))/2
        
    end = time.time()
    
    return the_sum, end-start  
In [63]:
sum_of_n3_timed(100)
Out[63]:
(5050.0, 3.0994415283203125e-06)

Timed Trials

In [86]:
for n in [10_000, 100_000, 1_000_000, 10_000_000]:
    for i in range(5):
        print("Sum of {0} is {1} required {2:10.7f} seconds.".format(n, *sum_of_n_timed(n)))
        
    print("-"*10)
        
    for i in range(5):
        print("Sum of {0} is {1} required {2:10.7f} seconds.".format(n, *sum_of_n3_timed(n)))
        
    print("\n\n")
Sum of 10000 is 50005000 required  0.0007062 seconds.
Sum of 10000 is 50005000 required  0.0019352 seconds.
Sum of 10000 is 50005000 required  0.0008121 seconds.
Sum of 10000 is 50005000 required  0.0006800 seconds.
Sum of 10000 is 50005000 required  0.0008330 seconds.
----------
Sum of 10000 is 50005000.0 required  0.0000010 seconds.
Sum of 10000 is 50005000.0 required  0.0000000 seconds.
Sum of 10000 is 50005000.0 required  0.0000000 seconds.
Sum of 10000 is 50005000.0 required  0.0000010 seconds.
Sum of 10000 is 50005000.0 required  0.0000010 seconds.



Sum of 100000 is 5000050000 required  0.0253398 seconds.
Sum of 100000 is 5000050000 required  0.0153768 seconds.
Sum of 100000 is 5000050000 required  0.0112960 seconds.
Sum of 100000 is 5000050000 required  0.0097141 seconds.
Sum of 100000 is 5000050000 required  0.0193412 seconds.
----------
Sum of 100000 is 5000050000.0 required  0.0000012 seconds.
Sum of 100000 is 5000050000.0 required  0.0000010 seconds.
Sum of 100000 is 5000050000.0 required  0.0000010 seconds.
Sum of 100000 is 5000050000.0 required  0.0000010 seconds.
Sum of 100000 is 5000050000.0 required  0.0000007 seconds.



Sum of 1000000 is 500000500000 required  0.1019647 seconds.
Sum of 1000000 is 500000500000 required  0.0890398 seconds.
Sum of 1000000 is 500000500000 required  0.1071601 seconds.
Sum of 1000000 is 500000500000 required  0.1228731 seconds.
Sum of 1000000 is 500000500000 required  0.0947618 seconds.
----------
Sum of 1000000 is 500000500000.0 required  0.0000019 seconds.
Sum of 1000000 is 500000500000.0 required  0.0000081 seconds.
Sum of 1000000 is 500000500000.0 required  0.0000000 seconds.
Sum of 1000000 is 500000500000.0 required  0.0000010 seconds.
Sum of 1000000 is 500000500000.0 required  0.0000000 seconds.



Sum of 10000000 is 50000005000000 required  1.0711317 seconds.
Sum of 10000000 is 50000005000000 required  1.2439430 seconds.
Sum of 10000000 is 50000005000000 required  1.2552941 seconds.
Sum of 10000000 is 50000005000000 required  0.9010460 seconds.
Sum of 10000000 is 50000005000000 required  1.1486373 seconds.
----------
Sum of 10000000 is 50000005000000.0 required  0.0000012 seconds.
Sum of 10000000 is 50000005000000.0 required  0.0000010 seconds.
Sum of 10000000 is 50000005000000.0 required  0.0000000 seconds.
Sum of 10000000 is 50000005000000.0 required  0.0000000 seconds.
Sum of 10000000 is 50000005000000.0 required  0.0000000 seconds.



$T(n) = 5n^2 + 27n + 1005 \rightarrow O(5n^2) \rightarrow O(n^2)$

In [96]:
for n in [10_000, 100_000, 1_000_000, 10_000_000]:
    print(f"Testing T(n) with n={n}")
    print(5*n**2, 27*n, 1005)
    print()
Testing T(n) with n=10000
500000000 270000 1005

Testing T(n) with n=100000
50000000000 2700000 1005

Testing T(n) with n=1000000
5000000000000 27000000 1005

Testing T(n) with n=10000000
500000000000000 270000000 1005

In [88]:
type(i*10**exp for exp in (2,9) for i in range(1,10))
Out[88]:
generator
In [101]:
# Python generator expression, closely related to comprehensions
generator = (i*10**exp for exp in range(2,9) for i in range(1,10))
In [100]:
for n in generator:
    print(f"Testing T(n) with n={n}")
    print(5*n**2, 27*n, 1005)
    print()
Testing T(n) with n=100
50000 2700 1005

Testing T(n) with n=200
200000 5400 1005

Testing T(n) with n=300
450000 8100 1005

Testing T(n) with n=400
800000 10800 1005

Testing T(n) with n=500
1250000 13500 1005

Testing T(n) with n=600
1800000 16200 1005

Testing T(n) with n=700
2450000 18900 1005

Testing T(n) with n=800
3200000 21600 1005

Testing T(n) with n=900
4050000 24300 1005

Testing T(n) with n=1000
5000000 27000 1005

Testing T(n) with n=2000
20000000 54000 1005

Testing T(n) with n=3000
45000000 81000 1005

Testing T(n) with n=4000
80000000 108000 1005

Testing T(n) with n=5000
125000000 135000 1005

Testing T(n) with n=6000
180000000 162000 1005

Testing T(n) with n=7000
245000000 189000 1005

Testing T(n) with n=8000
320000000 216000 1005

Testing T(n) with n=9000
405000000 243000 1005

Testing T(n) with n=10000
500000000 270000 1005

Testing T(n) with n=20000
2000000000 540000 1005

Testing T(n) with n=30000
4500000000 810000 1005

Testing T(n) with n=40000
8000000000 1080000 1005

Testing T(n) with n=50000
12500000000 1350000 1005

Testing T(n) with n=60000
18000000000 1620000 1005

Testing T(n) with n=70000
24500000000 1890000 1005

Testing T(n) with n=80000
32000000000 2160000 1005

Testing T(n) with n=90000
40500000000 2430000 1005

Testing T(n) with n=100000
50000000000 2700000 1005

Testing T(n) with n=200000
200000000000 5400000 1005

Testing T(n) with n=300000
450000000000 8100000 1005

Testing T(n) with n=400000
800000000000 10800000 1005

Testing T(n) with n=500000
1250000000000 13500000 1005

Testing T(n) with n=600000
1800000000000 16200000 1005

Testing T(n) with n=700000
2450000000000 18900000 1005

Testing T(n) with n=800000
3200000000000 21600000 1005

Testing T(n) with n=900000
4050000000000 24300000 1005

Testing T(n) with n=1000000
5000000000000 27000000 1005

Testing T(n) with n=2000000
20000000000000 54000000 1005

Testing T(n) with n=3000000
45000000000000 81000000 1005

Testing T(n) with n=4000000
80000000000000 108000000 1005

Testing T(n) with n=5000000
125000000000000 135000000 1005

Testing T(n) with n=6000000
180000000000000 162000000 1005

Testing T(n) with n=7000000
245000000000000 189000000 1005

Testing T(n) with n=8000000
320000000000000 216000000 1005

Testing T(n) with n=9000000
405000000000000 243000000 1005

Testing T(n) with n=10000000
500000000000000 270000000 1005

Testing T(n) with n=20000000
2000000000000000 540000000 1005

Testing T(n) with n=30000000
4500000000000000 810000000 1005

Testing T(n) with n=40000000
8000000000000000 1080000000 1005

Testing T(n) with n=50000000
12500000000000000 1350000000 1005

Testing T(n) with n=60000000
18000000000000000 1620000000 1005

Testing T(n) with n=70000000
24500000000000000 1890000000 1005

Testing T(n) with n=80000000
32000000000000000 2160000000 1005

Testing T(n) with n=90000000
40500000000000000 2430000000 1005

Testing T(n) with n=100000000
50000000000000000 2700000000 1005

Testing T(n) with n=200000000
200000000000000000 5400000000 1005

Testing T(n) with n=300000000
450000000000000000 8100000000 1005

Testing T(n) with n=400000000
800000000000000000 10800000000 1005

Testing T(n) with n=500000000
1250000000000000000 13500000000 1005

Testing T(n) with n=600000000
1800000000000000000 16200000000 1005

Testing T(n) with n=700000000
2450000000000000000 18900000000 1005

Testing T(n) with n=800000000
3200000000000000000 21600000000 1005

Testing T(n) with n=900000000
4050000000000000000 24300000000 1005

In [103]:
# By Abhijit
generator = (i*10**exp for exp in range (4,8) for i in range(1,2))
for n in generator:
    print(n)
10000
100000
1000000
10000000