[Calcolo Complessità] Albero Binario.

[Gin&&Tonic]

Ho un metodo "Verifica " che riceve un albero binario "A" . il metodo ritorna true se l'albero è uguale a null ,oppure se il valore contenuto nella radice è contenuto in un solo nodo dell'albero (oltre che nella radice ovviamente).

Il metodo è questo :

public static boolean verifica(AlberoBb<Integer> a) {
        if (a == null || contaOcc(a, a.getVal()) == 1)
            return true;
        return false;
    }


public static int contaOcc(AlberoBb<Integer> a, int x) {
        if (a == null)
            return 0;
        if (a.getVal() == x)
            return contaOcc(a.getSin(), x) + contaOcc(a.getDes(), x) + 1;
        return contaOcc(a.getSin(), x) + contaOcc(a.getDes(), x);
    }




getSin , getDes , e getVal hanno complessita 1

Devo calcolare complessità spaziale e temporale nel caso peggiore e caso migliore .

Io credo che la complessità temporale sia caso peggiore che nel caso migliore , siaN . ,dove N è il numero di nodi dell'albero ed il metodo deve visitare tutti nodi.

Spaziale : Caso migliore O(log N) albero binario bilanciato , Peggiore O(N)

Qualcuno può aiutarmi nel calcolo della complessità?

[Gin&&Tonic]

Nessuno sa dirmi se , il calcolo della complessità è giusto o sbagliato?