Complejidad algoritmo

2/N < 37 < < N log log N < N log N < N log N^2 < N log^2 N < N^1.5 < N^2< N^2 √N < N log N < N^3 < 2^(n/2) < 2^N

2)

A) sum = 0; 1 total= 2n+ 2 for (i =1; i <= n; i ++) n+1 sum += n; n orden= O(n)

B) int sum ( int n ) { int partialSum ; partialSum = 0; 1 total= 3+2n for( int i = 1; i <= n; ++ i ) n+1 partialSum += i * i * i; n orden= O(n) return partialSum ; 1 }

C) for( i = 0; i < n; ++ i ) n+1 total= 2n+2n^2 for( j = 0; j < n; ++ j ) n(n+1) ++ k; n(n) orden= O(n^2)

D) for( i = 0; i < n; ++ i) n+1 total= 2+4n+ 2n^2 a[ i ] = 0; n for( i = 0; i < n; ++ i) n+1 orden= O(n^2) for( j = 0; j < n; ++ j ) n(n+1) a[ i ] += a[ j ] + i + j; n*n

E) sum = 0; 1 for (i =1; i <= n; i ++) n+1 total= 3+5n+n^2 for (j =1; j <= i; j ++) n(n+1) sum ++; n orden= O(n^2) for (k =0; k <n; k ++) n+1 A[k] = k; n

F) sum1 = 0; 1 total= 4+4n+4n^2 for (i =1; i <= n; i ++) n+1 for (j =1; j <= n; j ++) n(n+1) sum1 ++; n*n orden= sum2 = 0; 1 for (i =1; i <= n; i ++) n+1

for (j =1; j <= i; j ++) n((n+1)/2) sum2 ++; n*n((n+1)/2)

G) sum1 = 0; 1 for (k =1; k <= n; k *=2) log2(N) total= for (j =1; j <= n; j ++) n+1 sum1 ++; n orden= sum2 = 0; 1 for (k =1; k <= n; k *=2) log2(N) for (j =1; j <= k; j ++) sum2 ++; n

H) int binary (int A [] , int n , int K) { int l = -1; 1 int r = n; 1 total= while (l +1 != r) { int i = (l+r) /2; if (K == A[i ]) return i; orden= if (K < A[i ]) r = i; else (K > A[i ]) l = i; } return n; }

I) long factorial ( int n ) { if( n <= 1 ) return 1; else return n * factorial ( n - 1 ); }

...