We analyzed the time complexity of different solutions for a given problem. Then, we proved several claims using the Formal definition of Big O.
Given a natural number $p$, how many right triangles exist with integer-sized sides whose perimeter is $p$?
How many triplets $(a,b,c)$ are there such that:
When computing code complexity, we
go over all triplets of numbers in the relevant range.
There are $(p-1)^3$ iterations.
Complexity: $O(p^3)$
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 and a+b+c==p and a**2+b**2==c**2:
cnt += 1
return cnt
instead of looping over $c$, use one of the constraints to set its value as a function of $a,b$. one less loop and one less condition.
There are $(p-1)^2$ iterations.
Complexity: $O(p^2)$
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**2+b**2==c**2:
cnt += 1
return cnt
define a lower bound for $b$. The loops are now dependent and, therefore, to compute the number of atomic operations, we take a sum over $a$ of the number of $b$ values tested.
The number of iterations is: $\sum_{a = 1}^{p-1} (p - (a+1)) = \frac{(p-1)(p-2)}{2}$
Complexity: $O(p^2)$.
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**2+b**2==c**2:
cnt += 1
return cnt
define an upper bound for $a,b$. we use the same strategy as in v3 to count operations.
$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).
The number of iterations is: $\sum_{a = 1}^{p/3} (\lfloor\frac{p-a}{2}\rfloor + 1 - (a+1))$
Complexity: $O(p^2)$.
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**2+b**2==c**2:
cnt += 1
return cnt
we realize we have two equations in three variables, therefore there’s only a single free parameter here.
$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 loop only over $a$, but need to make sure that the resulting $b$ is integral, and that $a<b$. Note that we do not have to calculate $c$ here
The number of iterations is: $p/3$
Complexity: $O(p)$
def number_of_integer_right_triangles_v5(p):
cnt = 0
for a in range(1, p//3+1):
b = (p**2-2*p*a)/(2*(p-a))
if int(b)==b and a<b:
cnt += 1
return cnt
We compare the change in running time of each of the functions as $p$ increases twofold.
As expected, when $p$ increases by 2 and for large enough $p$ (so that asymptotic computations are valid):
the cubical version ($O(p^3)$) takes x ~$2^3$ longer,
the quadratic versions ($O(p^2)$) takes x ~$2^2$ longer,
and the linear version ($O(p)$) takes x ~2 longer.
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.3234666596139846 secs v2, p = 240 took 0.04294541250200723 secs v3, p = 240 took 0.03771628332745536 secs v4, p = 240 took 0.006203349058495178 secs v5, p = 240 took 9.513249270298729e-05 secs v1, p = 480 took 11.197607950707948 secs v2, p = 480 took 0.1921735564039011 secs v3, p = 480 took 0.19173342059733045 secs v4, p = 480 took 0.025842485065965093 secs v5, p = 480 took 0.00017605432262257636 secs
Given two functions $f(n)$ and $g(n)$,
$f(n) = O(g(n))$
If and only if there exist $c > 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.