Détermination de la complexité pour les fonctions récursives (notation Big O)

Question

J'ai un partiel d'informatique demain et j'ai besoin d'aide pour déterminer la complexité de ces fonctions récursives. Je sais comment résoudre des cas simples, mais j'essaie toujours d'apprendre comment résoudre ces cas plus difficiles. Ce ne sont que quelques exemples de problèmes que je n'ai pas pu résoudre. Toute aide serait très appréciée et m'aiderait grandement dans mes études, merci !

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

Answer 1

Je vois que pour la réponse acceptée (recursivefn5), certaines personnes ont des problèmes avec l'explication. Je vais donc essayer de clarifier au mieux de mes connaissances.

1. La boucle for s'exécute pendant n/2 fois parce qu'à chaque itération, nous augmentons i (le compteur) d'un facteur 2. Ainsi, disons que n = 10, la boucle for s'exécutera 10/2 = 5 fois, c'est-à-dire lorsque i vaut respectivement 0, 2, 4, 6 et 8.

2. De la même manière, l'appel récursif est réduit d'un facteur 5 à chaque fois qu'il est appelé, c'est-à-dire qu'il est exécuté n/5 fois. Supposons à nouveau que n = 10, l'appel récursif s'exécute 10/5 = 2 fois, c'est-à-dire lorsque n est égal à 10 et 5, puis il atteint le cas de base et se termine.

3. En calculant le temps d'exécution total, la boucle for s'exécute n/2 fois à chaque fois que nous appelons la fonction récursive. Comme la fonction récursive fxn s'exécute n/5 fois (dans 2 ci-dessus), la boucle for s'exécute (n/2) * (n/5) = (n^2)/10 fois, ce qui se traduit par un temps d'exécution global de Big O de O(n^2) - en ignorant la constante (1/10)...