In [3]:
import time
def sumOfN(n):
start = time.time()
theSum = 0
for i in range(1,n+1):
theSum = theSum + i
end = time.time()
return theSum,end-start
for i in range(5):
print("Sum is %d required %10.7f seconds"%sumOfN(1000000))
The order of magnitude function describes the part of T(n) that increases the fastest as the value of n increases. Order of magnitude is often called Big-O notation (for “order”) and written as O(f(n)).
It provides a useful approximation to the actual number of steps in the computation. The function f(n) provides a simple representation of the dominant part of the original T(n).
As another example, suppose that for some algorithm, the exact number of steps is
T(n)=5nˆ2+27n+1005
When n is small, say 1 or 2, the constant 1005 seems to be the dominant part of the function. However, as n gets larger, the nˆ2 term becomes the most important.
In fact, when n is really large, the other two terms become insignificant in the role that they play in determining the final result
Again, to approximate T(n) as n gets large, we can ignore the other terms and focus on 5nˆ2.
In addition, the coefficient 5 becomes insignificant as n gets large.
We would say then that the function T(n) has an order of magnitude f(n)=n2, or simply that it is O(n2).
| f(n) | Name |
|---|---|
| 1 | Constant |
| log n | Logarithmic |
| n | Linear |
| n log n | Log Linear |
| nˆ2 | Quadratic |
| nˆ3 | Cubic |
| 2ˆn | Exponential |
In [12]:
import matplotlib.pyplot as plt
import math
n = 11
x = list(range(1,n))
linear = [x for x in range(1, n)]
Quadratic = [x**2 for x in range(1, n)]
LogLinear = [x * math.log(x) for x in range(1, n)]
Cubic = [x**3 for x in range(1, n)]
Exponential = [2**x for x in range(1, n)]
logarithmic = [math.log(x) for x in range(1, n)]
plt.plot(x, linear,'k--', label='linear')
plt.plot(x, Quadratic, 'k:', label='Quadratic')
plt.plot(x, LogLinear, 'y', label='LogLinear')
plt.plot(x, Cubic, 'b', label='Cubic')
plt.plot(x, Exponential, 'r', label='Exponential')
plt.plot(x, logarithmic, 'g', label='logarithmic')
legend = plt.legend(shadow=True)
plt.grid(True)
plt.show()
In [13]:
a=5
b=6
c=10
n = 100
for i in range(n):
for j in range(n):
x = i * i
y = j * j
z = i * j
for k in range(n):
w = a*k + 45
v = b*b
d = 33
The number of assignment operations is the sum of four terms.
This gives us T(n)=3+3n2+2n+1=3nˆ2+2n+4.
In [14]:
import timeit
def test1():
l = []
for i in range(1000):
l = l + [i]
def test2():
l = []
for i in range(1000):
l.append(i)
def test3():
l = [i for i in range(1000)]
def test4():
l = list(range(1000))
t1 = timeit.Timer("test1()", "from __main__ import test1")
print("concat ",t1.timeit(number=1000), "milliseconds")
t2 = timeit.Timer("test2()", "from __main__ import test2")
print("append ",t2.timeit(number=1000), "milliseconds")
t3 = timeit.Timer("test3()", "from __main__ import test3")
print("comprehension ",t3.timeit(number=1000), "milliseconds")
t4 = timeit.Timer("test4()", "from __main__ import test4")
print("list range ",t4.timeit(number=1000), "milliseconds")
| Operation | Big-O Efficiency |
|---|---|
| index [] | O(1) |
| index assignment | O(1) |
| append | O(1) |
| pop() | O(1) |
| pop(i) | O(n) |
| insert(i,item) | O(n) |
| del operator | O(n) |
| iteration | O(n) |
| contains (in) | O(n) |
| get slice [x:y] | O(k) |
| del slice | O(n) |
| set slice | O(n+k) |
| reverse | O(n) |
| concatenate | O(k) |
| sort | O(n log n) |
| multiply | O(nk) |
In [15]:
popzero = timeit.Timer("x.pop(0)",
"from __main__ import x")
popend = timeit.Timer("x.pop()",
"from __main__ import x")
x = list(range(2000000))
print(popzero.timeit(number=1000))
x = list(range(2000000))
print(popend.timeit(number=1000))
| operation | Big-O Efficiency |
|---|---|
| copy | O(n) |
| get item | O(1) |
| set item | O(1) |
| delete item | O(1) |
| contains (in) | O(1) |
| iteration | O(n) |
In [16]:
import timeit
import random
for i in range(10000,1000001,20000):
t = timeit.Timer("random.randrange(%d) in x" % i,
"from __main__ import random, x")
x = list(range(i))
lst_time = t.timeit(number=1000)
x = {j:None for j in range(i)}
d_time = t.timeit(number=1000)
print("%d,%10.3f,%10.3f" % (i, lst_time, d_time))
In [ ]: