Pour résoudre la relation de récurrence 
𝑇
(
𝑛
)
=
3
𝑇
(
𝑛
3
)
+
𝑛
T(n)=3T(
3
n
	​

)+n, nous allons utiliser le théorème de Maître (Master Theorem). Ce théorème permet de déterminer la complexité asymptotique des relations de récurrence de la forme :

\[
T(n) = aT\left(\frac{n}{b}\right) + f(n)
\]

où 
𝑎
≥
1
a≥1, 
𝑏
>
1
b>1, et 
𝑓
(
𝑛
)
f(n) est une fonction asymptotiquement positive.

Étape 1 : Identifier les paramètres 
𝑎
a, 
𝑏
b, et 
𝑓
(
𝑛
)
f(n)
Pour notre relation :

𝑎
=
3
a=3

𝑏
=
3
b=3

𝑓
(
𝑛
)
=
𝑛
f(n)=n

Étape 2 : Comparer 
𝑓
(
𝑛
)
f(n) avec 
𝑛
log
⁡
𝑏
𝑎
n
log
b
	​

a

Calculons 
𝑛
log
⁡
𝑏
𝑎
n
log
b
	​

a
 :
\[
\log_b a = \log_3 3 = 1
\]
Donc,
\[
n^{\log_b a} = n^1 = n
\]

Nous avons donc 
𝑓
(
𝑛
)
=
𝑛
f(n)=n, ce qui signifie que 
𝑓
(
𝑛
)
=
Θ
(
𝑛
log
⁡
𝑏
𝑎
)
f(n)=Θ(n
log
b
	​

a
).

Étape 3 : Appliquer le théorème de Maître
Le théorème de Maître stipule que si 
𝑓
(
𝑛
)
=
Θ
(
𝑛
log
⁡
𝑏
𝑎
)
f(n)=Θ(n
log
b
	​

a
), alors :

\[
T(n) = \Theta(n^{\log_b a} \log n) = \Theta(n \log n)
\]

Conclusion
La solution de la relation de récurrence 
𝑇
(
𝑛
)
=
3
𝑇
(
𝑛
3
)
+
𝑛
T(n)=3T(
3
n
	​

)+n est :

\[
T(n) = \Theta(n \log n)
\]