We analyzed the time complexity of different solutions for a given problem. Then, we proved several claims using the Formal definition of Big O.

- The time complexity bound implies how that the running time changes as a function of the input size.
- Two solutions that have the same time complexity bound may differ in their running time (one can be more efficient than the other).
- The Big O notation "hides" additive and multiplicative constants
- Two solutions that have the same time complexity bound may differ in their running time (one can be more efficient than the other).
- To analyze nested loops that are dependent, use a sum ($\sum$), with the boundaries of the external loop as the limits and the number of iterations for the inner loop in the sum itself.

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:

- $a^2 +b^2 == c^2$
- $a + b + c == p$
- $a,b,c > 0$ are all integers

- $a \neq b$ and $b \neq c$
- The case $a = b$ cannot hold as this would imply $2a^2 = c^2 \implies c = \sqrt{2} a$
- The condition $b < c$ is redundant (since we require that $a,b,c > 0$ and $a^2 + b^2 == c^2$)

When computing code complexity, we

- define the entire content of the innermost loop as an “atomic operation” which takes constant time.
- describe the complexity as a function of $p$ (i.e., use $p$ as the “problem size” or “input size”). Note, however, that the formal definition of “problem size” for a numeric input is the size it takes to represent the input, i.e. $n = \log(p)$. Working with $p$ here is easier and more intuitive.

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)$

In [1]:

```
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)$

In [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)$.

In [3]:

```
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)$.

In [4]:

```
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)$

In [5]:

```
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.

In [8]:

```
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")
```

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 :

- Constant - $O(1)$
- Logarithmic - $O(\log(n))$
- Poly-logarithmic - $O(\log^c(n))$ for $c > 1$
- Root/fractional - $O(n^{1/c})$ for $c>1$
- Linear - $O(n)$
- Loglinear - $O(n \log(n))$
- Polynomial - $O(n^{c})$ for $c>1$
- Exponential - $O(c^{n})$ for $c>1$

See also this list on Wikipedia.

Transitivity:

- If $f(n) = O(g(n))$ and $g(n) = O(h(n))$ then $f(n) = O(h(n))$

Non-symmetry:

- $f(n) = O(g(n))$ does not imply $g(n) = O(f(n))$ or $g(n) \neq O(f(n))$

- $2^n = O(2^{n/2})$
- Wrong, assume there exists $n_0, c>0$ such that for $n > n_0$ $2^n \leq c \cdot 2^{n/2}$. This implies $c \geq 2^{n/2} \to \infty$ as $n \to \infty$ in contradiction to $c$ being constant.

- $\log n! = O(n \cdot \log n)$
- True. Note that as $\log(\cdot)$ is monotone increasing and that $\log (ab) = \log a + \log b$, thus: $\log n! = \log 1 + \ldots + \log n = \sum_{i=1}^n \log i \leq \sum_{i=1}^n \log n = n \cdot \log n$

- If $f_1(n) = O(g_1(n)), f_2(n) = O(g_2(n))$ then $f_1(n) + f_2(n) = O(g_1(n)+g_2(n)) = O(\max \{g_1(n),g_2(n)\})$
- True. Let $n_1, c_1$ and $n_2, c_2$ be the constants such that $n > n_1 \implies f_1(n) \leq c_1 g_1(n)$ and $n > n_2 \implies f_2(n) \leq c_2 g_2(n)$ and note that for $n_3 = n_1 + n_2$ we have that if $n > n_3$: $$f_1(n) + f_2(n) \leq c_1 g_1(n) + c_2 g_2(n) \leq (c_1 + c_2) (g_1(n) + g_2(n)) \leq 2 (c_1 + c_2) \max\{g_1(n),g_2(n)\}$$ Thus the first claim holds with constants $n_3, (c_1 + c_2)$ and the second with $n_3, 2(c_1 + c_2)$
- The above is also true for any $k$ functions $f_1, \ldots, f_k$ where $k$ is a constant. A direct consequence of which is:

- For any constant $k \geq 1$ and constants $a_0, \ldots, a_k \in \mathbb{R}$: $$f(n) = a_0 \cdot n^0 + a_1 \cdot n^1 + \cdots + a_k\cdot n^k = O(n^k)$$
- True. Let $a_\max = \max\{|a_0|,\ldots,|a_k|\}$ and observe that $f(n) \leq a_\max n^0 + a_\max n^1 + \cdots + a_\max n^k = k a_\max n^k$. The claim follows as $k a_\max$ is a constant

- For any constant $k > 1$: $\log_2^k n = O\left(\log_{10}^k n\right)$
- True. Basic logarithm identities show us that $\log_2^k n = \left(\frac{\log_{10} n}{ \log_{10} 2}\right)^k = \left(\frac{1}{ \log_{10} 2}\right)^k \cdot \log_{10}^k n$. The claim follows as $\left(\frac{1}{ \log_{10} 2}\right)^k$ is a constant.
- Letting $k = 1$ we can generalize the above: for any constants $a,b$ we have both $\log_a n = O(\log_b n)$ and $\log_b n = O(\log_a n)$. Because of this, we usually omit the base of the logarithm when using $O(\cdot)$ notation (if it is constant!) and simply say $O(\log n)$

- For any two functions $f,g$, $f(n) = O(g(n)) \implies 2^{f(n)} = O(2^{g(n)})$
- Wrong. Letting $f(n) = n, g(n) = n/2$ this is the first example from the previous section.

- $\sum_{i = 0}^{\log n}\frac{i}{2^n} = O(1)$
- True. We first see that $\sum_{i = 0}^{\log n}\frac{i}{2^n} \leq \frac{\log^2 n}{2^n} = \frac{2^{\log \log^2 n}}{2^n} =\frac{2^{2\log \log n}}{2^n}$ The claim follows by noting that for large enough $n$ we have: $n > \log \log n$)

In [ ]:

```
```