---
title: "cpxa - TD 1 : "
tags: cpxa, td
---
{%hackmd theme-dark %}

$$
\newcommand{\vt}[3]{
\begin{pmatrix}
{#1} \\
{#2} \\
{#3}
\end{pmatrix}
}
\newcommand{\limto}[1]{\xrightarrow[#1]{}}
$$

# Complexité des algorithme - TD 1 : Subject

## Exercice 1.1

1)
$\forall n \in \mathbb N^\star$
$$
\begin{align}
S &= \sum_{i = 0}^{n - 1} \sum_{j = 1}^n 1 \\
S &= \sum_{i = 0}^{n - 1} n\\
S &= n^2\\
\end{align}
$$

2)
$$
\begin{align}
S &= \sum_{i = 0}^{n - 1} \sum_{j = 1}^{\lfloor n/2 \rfloor} 1 \\
S &= \sum_{i = 0}^{n - 1} \lfloor n/2 \rfloor \\
S &= n \lfloor n/2\rfloor \\
\end{align}
$$

3)
$$
\begin{align}
S &= \sum_{i = 0}^{n - 1} \sum_{j = 0}^i 1\\
S &= \sum_{i = 0}^{n - 1} i + 1\\
&\text{ nb de term}\times\text{(1ere term + dernier term)}\\
S &= \frac{n (1 + n)} 2
\end{align}
$$

4)
changement de variable:
$$
1 \le j \le n - 1\\
1 \le 2^k \le n - 1\\
\log_2(1) \le k \le \log_2(n - 1)\\
0 \le k \le \lfloor\log_2(n - 1)\rfloor
$$

$$
\begin{align}
S &= \sum_{i = 0}^{n - 1} \sum_{j = \lfloor\log_2(1)\rfloor}^{\lfloor \log_2(n - 1)\rfloor} 1\\
S &= \sum_{i = 0}^{n - 1} \lfloor\log_2(n - 1)\rfloor - \lfloor\log_2(1)\rfloor + 1\\
S &= \sum_{i = 0}^{n - 1} \lfloor\log_2(n - 1)\rfloor + 1\\
S &= n (1 + \lfloor \log_2(n - 1) \rfloor) = n \lceil \log_2(n) \rceil\\
\end{align}
$$

5)

$i$ pas jusqu'a $n - 1$ mais jusqua $n - 3$ car les dernier tours de boucle ne serve a rien (0 tous de la derniere boucle)
$$
\begin{align}
S &= \sum_{i = 0}^{n - 3} \sum_{j = i}^{n - 3} 1\\
S &= \sum_{i = 0}^{n - 3} (n - 3 - i + 1)\\
S &= \sum_{i = 0}^{n - 3} (n - i - 2)\\
S &= \frac{(n - 2)((n - 2) + 1)} 2\\
S &= \frac{(n - 2)(n - 1)} 2\\
\end{align}
$$

6)
skip

## Exercice 1.2

$$
S = \sum_{y = 0}^{n - 1} S_1 + S_2\\
S = n \times( S_1 + S_2)
$$

on as donc
$$
S_1 = \sum_{x = n - y}^{n + y} 1\\
S_1 = 2y + 1
$$

et
$$
S_2 = \sum_{x = 1}^{2n -1} = 2n - 1
$$

ce qui nous done
$$
S = (n -1)(2n - 1) + n^2
$$

## Exerice 1.3

1)
$$
S = \sum_{i = 0}^{999} 2i + 1\\
S = \frac{1000 (1 + 1999)} 2 = 1\times 10^6
$$

2)

$$
\begin{align}
42 &= 10^{1.\dots}\\
42 &= 10^1 \times 10^{0.\dots}\\
4.2 &= 10^{0.\dots}\\
4.2^{10} &= 10^{\dots.\dots}\\
1 708 019 &= 10^{6.\dots}\\
1.708 019 &= 10^{0.\dots}\\
1.708 019^10 &= 10^{\dots}\\
211.\dots &= 10^{2,\dots}\\
log_{10}(42) &\simeq 1,62\\
\end{align}
$$

## Exercice 1.4