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, count only those where the above conditions hold.
There are $p-1$ options for each variable $a,b,c$, so we need $(p-1)^3$ iterations and we can check each triplet in constant time.
Complexity: $O(p^3)$
def num_of_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
If we look at a pair of values for $a, b$, we can compute $c$ directly instead of going over all possible $c$ values in $\{1,2,\ldots,p-1\}$.
We now use two nested loops instead of three (and omit the condition $a + b + c = p$).
There are $(p-1)^2$ iterations, each one is again computed in constant time.
Complexity: $O(p^2)$
def num_of_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 and c > 0:
cnt += 1
return cnt
Since we require $a < b$, in each iteration of the outer loop for $a$ we can define a lower bound for $b$, i.e. - in each iteration we need to check $b$ values between $a+1,\ldots, p-1$ instead of $1,\ldots,p-1$.
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.
In the $i$th iteration of $a$ (that is, for $a=i$) we need to check $p - 1 - i = p - (1 + i)$ values of $b$, so the total number of iterations is: $$\sum_{a = 1}^{p-1} (p - (1 + a)) = \sum_{i = 0}^{p-2} i = \frac{(p-1)(p-2)}{2} $$
Complexity: $O(p^2)$.
def num_of_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 and c > 0:
cnt += 1
return cnt
We now further improve our efficiency by defining upper bounds for $a,b$. we use the same strategy as in v3 to count operations.
First of all, since $a < b < c$ and $a + b + c = p$, clearly $a < p/3$. That is, the maximal possible value of $a$ is $p//3$ (we will iterate till $p//3 + 1$ in order to include $p//3$ in the range).
Next, $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$ (again, we iterate till $(p-a)//2 + 1$ in order to include $(p-a)//2$ in the range).
The number of iterations is therefore: $$\sum_{a = 1}^{p/3} \left(\left\lfloor\frac{p-a}{2}\right\rfloor + 1 - (a+1)\right)\approx \sum_{a = 1}^{p/3} \frac{p}{2} - \frac{a}{2} - a =\frac{p^2}{6} - \frac{3}{2}\sum_{a = 1}^{p/3}a = \frac{p^2}{6} - \frac{3}{2}(p/3 + 1)\cdot \frac{p}{6} = \frac{p^2}{6} - \frac{p^2}{12} - \frac{p}{4} = \frac{p^2}{12} - \frac{p}{4}$$
Complexity: $O(p^2)$.
def num_of_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$ to get $a^2 + b^2 = (p -a -b)^2$, open and isolate $b$ to get $b = \frac{p^2-2ap}{2(p-a)}$.
So what do we need to do? 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$ and in each iteration we still do only a constant number of operations!
Complexity: $O(p)$
def num_of_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)$) runs in time which is roughly $2^3 = 8$ times longer,
the quadratic versions ($O(p^2)$) runs in time which is roughly $2^2 = 4$ times longer,
and the linear version ($O(p)$) runs in time which is roughly $2$ times 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.perf_counter()
for i in range(number):
x = eval(expression)
t2=time.perf_counter()
return t2-t1
print("v1, p = 240 took",elapsed("num_of_triangles_v1(240)"), "secs")
print("v2, p = 240 took",elapsed("num_of_triangles_v2(240)"), "secs")
print("v3, p = 240 took",elapsed("num_of_triangles_v3(240)"), "secs")
print("v4, p = 240 took",elapsed("num_of_triangles_v4(240)"), "secs")
print("v5, p = 240 took",elapsed("num_of_triangles_v5(240)"), "secs")
print("")
print("v1, p = 480 took",elapsed("num_of_triangles_v1(480)"), "secs")
print("v2, p = 480 took",elapsed("num_of_triangles_v2(480)"), "secs")
print("v3, p = 480 took",elapsed("num_of_triangles_v3(480)"), "secs")
print("v4, p = 480 took",elapsed("num_of_triangles_v4(480)"), "secs")
print("v5, p = 480 took",elapsed("num_of_triangles_v5(480)"), "secs")
print("")
print("Since v5 is too fast for some machines to time, we check it for input size which is x100 and x200 bigger:")
print("v5, p = 24000 took",elapsed("num_of_triangles_v5(24000)"), "secs")
print("v5, p = 48000 took",elapsed("num_of_triangles_v5(48000)"), "secs")
v1, p = 240 took 2.0098203190000277 secs v2, p = 240 took 0.07364331099995525 secs v3, p = 240 took 0.055745446999935666 secs v4, p = 240 took 0.013294021999968209 secs v5, p = 240 took 0.00012039499995353253 secs v1, p = 480 took 17.873038491999978 secs v2, p = 480 took 0.337060590999954 secs v3, p = 480 took 0.3156459970000469 secs v4, p = 480 took 0.044534067999961735 secs v5, p = 480 took 0.00019973799999206676 secs Since v5 is too fast for some machines to time, we check it for input size which is x100 and x200 bigger: v5, p = 24000 took 0.01722720300006131 secs v5, p = 48000 took 0.03454993299999387 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)|$
When $f,g$ are positive, an equivalent condition which is sometimes easier to check is that $$f(n) = O(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} < \infty$$
Let $n$ denote the size of the input and $c$ denote a constant. The most common time complexities we encounter are :
See also this list on Wikipedia.
Transitivity:
Non-symmetry: