We talked about comlexity. First we had an intuitive intro through an exercise and then we formally defined the notion of $O$ and solved some theoretical exercises.
How many triplets (a,b,c) are there such that:
When computing code complexity, we
def number_of_integer_right_triangles_v1(p):
cnt = 0
for a in range(1,p):
for b in range(1,p):
for c in range(1,p):
if a + b + c == p and a < b and a*a + b*b == c*c:
cnt += 1
return cnt
Once we set $a,b$ and $p$, $c$ is already defined!
def number_of_integer_right_triangles_v2(p):
cnt = 0
for a in range(1,p):
for b in range(1,p):
c = p - a - b
if a < b and a*a + b*b == c*c:
cnt += 1
return cnt
We require $a<b$, so just start $b$'s loop from $a+1$
def number_of_integer_right_triangles_v3(p):
cnt = 0
for a in range(1,p):
for b in range(a+1,p):
c = p - a - b
if a*a + b*b == c*c:
cnt += 1
return cnt
The loop are now dependent, so the number of iterations is: $\sum_{a = 1}^{p-1} (p - (a+1)) = \frac{(p-1)(p-2)}{2}$
The complexity is again $O(p^2)$ (squared complexity)
$a = p-b-c < p-2a \implies 3a < p$. Thus: $a < p/3$, that is, the maximal possible value of $a$ is $p//3$ (we add $1$ in order to include $p//3$ in the range).
$b = p-a-c < p-a-b \implies 2b < (p-a)$. Thus: $b < (p-a)/2$, that is, the maximal possible value of $b$ is $(p-a)//2$ (we add 1 in order to include (p-a)//2 in the range).
def number_of_integer_right_triangles_v4(p):
cnt = 0
for a in range(1,p//3 + 1):
for b in range(a+1,(p-a)//2 + 1):
c = p - a - b
if a*a + b*b == c*c:
cnt += 1
return cnt
The number of iterations is: $\sum_{a = 1}^{p/3} (\lfloor\frac{p-a}{2}\rfloor + 1 - (a+1))$
The complexity is again $O(p^2)$ (squared complexity)
$a+b+c=p \implies c = p-a-b$.
Substitute $c$ with $p-a-b$ in $a^2+b^2=c^2$ and isolate $b$ to get $b = \frac{p^2-2ap}{2(p-a)}$.
We don't even need to calculate c here!
def number_of_integer_right_triangles_v5(p):
cnt = 0
for a in range(1,p//3 + 1):
b = (p**2 - 2*a*p) / (2*(p-a))
if b == int(b) and a < b:
cnt += 1
return cnt
For the input $p=240$: the runtimes rank: $v_1, v_2, v_3, v_4, v_5$.
Once we double the input to $p=480$, the increase in runtime for $v_1$ is quadric (i.e. the runtimes is $2^3 = 8$ times slower), for $v_2,v_3,v_4$ its squared (i.e. the runtimes are $2^2=4$ times slower), and for $v_5$ its doubled.
import time
def elapsed(expression,number=1):
''' computes elapsed time for executing code
number of times (default is 1 time). expression should
be a string representing a Python expression. '''
t1=time.clock()
for i in range(number):
x = eval(expression)
t2=time.clock()
return t2-t1
print("v1, p = 240 took",elapsed("number_of_integer_right_triangles_v1(240)"), "secs")
print("v2, p = 240 took",elapsed("number_of_integer_right_triangles_v2(240)"), "secs")
print("v3, p = 240 took",elapsed("number_of_integer_right_triangles_v3(240)"), "secs")
print("v4, p = 240 took",elapsed("number_of_integer_right_triangles_v4(240)"), "secs")
print("v5, p = 240 took",elapsed("number_of_integer_right_triangles_v5(240)"), "secs")
print("")
print("v1, p = 480 took",elapsed("number_of_integer_right_triangles_v1(480)"), "secs")
print("v2, p = 480 took",elapsed("number_of_integer_right_triangles_v2(480)"), "secs")
print("v3, p = 480 took",elapsed("number_of_integer_right_triangles_v3(480)"), "secs")
print("v4, p = 480 took",elapsed("number_of_integer_right_triangles_v4(480)"), "secs")
print("v5, p = 480 took",elapsed("number_of_integer_right_triangles_v5(480)"), "secs")
v1, p = 240 took 1.601157981541931 secs v2, p = 240 took 0.010859777806814463 secs v3, p = 240 took 0.006627583046110885 secs v4, p = 240 took 0.0012292747397566473 secs v5, p = 240 took 8.447809707945453e-05 secs v1, p = 480 took 11.816460675643185 secs v2, p = 480 took 0.04442245206757889 secs v3, p = 480 took 0.029284687634344664 secs v4, p = 480 took 0.005004340358311765 secs v5, p = 480 took 0.00014763929115702012 secs
Given two functions $f(n)$ and $g(n)$,
$f(n) = O(g(n))$
If and only if there exist $c \geq 0 $ and $n_{0}\in \mathbb{R}$ such that
$\forall n>n_0$
$|f(n)| \leq c\cdot|g(n)|$
Let $n$ denote the size of the input. The most common time complexities we encounter are :
See also this list on Wikipedia.