Complexité d'algorithmes

Bonsoir !

J'ai du mal à comprendre la notion de complexité d'algorithmes. Par exemple, ici, je dois trouver la complexité des 4 algo' ci-dessous. Le premier n'étant pas récursif, je pense avoir trouvé qu'il s'agit d'une complexité O(n). Par contre, pour les 3 autres, je ne sais pas par où commencer...
En cours, j'ai vu la méthode des arbres récursifs à partir d'une expression T(n) donnée. Or, ici, je n'arrive pas à trouver l'expression de T(n) à partir des algo...
J'ai donc essayer de trouver leur complexité un peu "à l'oeil" en essayant de comprendre comment fonctionnait chaque algorithme et j'en suis arrivée à trouver une complexité en O(n) pour le troisième, et en O(log(n)) pour les 2 autres.


Quelqu'un pourrait-il me valider ces résultats ?
Et, le cas échéant, m'expliquer comment je suis censé procéder pour trouver la complexité d'algo récursifs ?

public class Math{

    public static int multiIter(int x, int y){ 
        int sum = 0;
        for (int i=0; i<y; i++) {
            sum += x;
        }
        return sum;  
    } 

    public static int multiRec(int x, int y){ 
        if  (x == 0){
            return 0;
        }
        else if (x%2 == 0){
            return 2*multiRec(x/2, y);
        }
        else{
            return 2*multiRec((x-1)/2, y)+y;
        }
    } 

    public static int puissanceRec(int x, int n){ 
        if (n==0){
            return 1;
        }
        else{
            return puissanceRec(x,n-1)*x;
        }
    } 

    public static int exponentiationRapide(int x, int n){ 
        if (n==0){
            return 1;
        }
        else if (n%2 == 0){
            return exponentiationRapide(x*x, n/2);
        }
        else{
            return exponentiationRapide(x*x, (n-1)/2)*x;
        } 
    }     
}