[Algoritmi] Complessità di due brevi algoritmi

[absinth]

Ciao a tutti! Ho difficoltà nella risoluzione di due mini esercizi sulla complessità di due algoritmi. Anche se sono apparentemente facili non avendo le soluzioni non sono sicuro.

[size=150]1) Esprimere la complessità di:[/size]

int g(int n)
{
	int a=n;
	if(n<=500)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				a+=n;
	else
		for(int i=1; i<=n; i++)
				a+=n;
	return a;
}

Per complessità credo che intenda le prestazioni temporali asintotiche.
$\{(O(n^2)\text{ per } n<=500),(O(n)\text{ per } n>500):}$
Quindi cosa bisogna concludere sulle prestazioni complessive? Si lascia la funzione definita per casi?

[size=150]2) Considerare il seguente algoritmo:[/size]

for( int bound = 1; bound <= n; bound *= 2){
	for( int i = 0; i < bound; i++){
		for( int j = 0; j < n; j += 2){
			...// constant number of operations
		}
		for( int j = 1; j < n; j *= 2){
			...// constant number of operations
		}
	}
}

Consegna: Spiegate allo studente C. Trullo perché la sua soluzione
$O(n^2 \logn)$ non è ottimale, ma è possibile ottenere approssimazione migliore.

Per il secondo ho ragionato in questo modo: trovo intanto la complessità dell'algoritmo senza i due cicli interni (che hanno j come contatore). Allora ho che bound cresce esponenzialmente per $k$ cicli tali che $bound=2^k <= n \implies k <=\log_2 n$
Per ognuno dei $k$ cicli ho quello interno che arriva fino a $2^k$ iterazioni.
$1+2+4+...+2^k=\frac{1-2^{k+1}}{1-2} \cong 2^{k+1}=2*2^{\log_2n}=2n$ (geometrica)
Gli altri due cicli interni aggiungo un ritardo complessivo $O(n/2+\log_2n)$
Allora le prestazioni dell'algoritmo sono: $O(2n(n/2+log_2n))=O(n^2+2nlog_2n)\cong O(n^2+nlog_2n)$
Asintoticamente diventa $O(n^2)$ Anche secondo voi è questa la vera complessità dell'algoritmo?

[apatriarca]

1. La risposta è semplicemente \(O(n)\) in quanto l'analisi asintotica riguarda solo il comportamento all'infinito.
2. Sì.

[absinth]

Grazie