big O - récursivité au lieu de multiplication - java, récursivité, big-o

Travailler sur une méthode pour remplacer la multiplication.

public static int mult(int num, int repeat){
if (repeat == 0) return 0;
if (repeat == 1) return num;
return num + mult(num, repeat - 1);
}

En termes de complexité temporelle et spatiale, s'agirait-il de temps O (k) où k est le répéter et O (1) espace?

Réponses:

Il est temps O (K) que vous appellerez cette fonction une fois par repeat et chaque appel est O (1). Cependant, c’est aussi un espace O (k) a, vous aurez k trames de pile avant que vous n’atteigniez la condition finale (en l’absence d’optimisation de la récursion d’appel final).