Dato che questo è chiaramente compito a casa, non ho intenzione di buttare le risposte là fuori, ma ti darò alcuni suggerimenti per affrontarle.
Per il tuo primo problema, devi ripensare alla definizione di un logaritmo. Quale sarebbe la risposta se fosse questo?
2^(log base2 (n))
Se inserisco quattro in per n, il log valuterà a due. Il potere dovrebbe quindi valutare a quattro. Se inserisco 8 in, ottengo 8. In altre parole, qualsiasi base b elevata alla base di log b di qualsiasi valore n restituisce < em> n . L'esponenziazione e il log si annullano a vicenda con la stessa base .
Cosa succede se l'esponenziazione ha una base più ampia del logaritmo? Base più piccola? Quanto velocemente crescono i polinomi rispetto a quelli in elevazione e registri indipendentemente dalla base?
Per il secondo problema, cosa succede quando applichi un esponenziale o fattoriale a una funzione che è polinomiale o inferiore? Ciò che domina a lungo termine, assumendo che tu non stia facendo 2 ^ (log 2 (n)) o qualcos'altro che annulla?
Ricorda che con Big-Oh devi pensare a tendenze arbitrariamente grandi. Numeri non specifici, basti pensare che se guardassi in basso all'asse n trilioni di valori, qual è il fattore dominante? Potrei tracciare 1.00000000000000000000000001 n e rimarrà molto piccolo per un tempo lungo ma alla fine crescerà più velocemente di n 10000000000000000 . Concesso in pratica il primo è preferibile al secondo, ma qui stiamo parlando di teoria, non di algoritmi di qualità di produzione.