Somatórios e exemplos

Conceito de OPERAÇÃO RELEVANTE: A op. relevante é a operação básica mais importante do código que representa seu custo. Numa inicialização de vetor, por exemplo, a operação relevante é a atribuição. Em geral, a op. relevante tem a ver com a semântica (significado; função) do código.
A complexidade do algoritmo muitas vezes é representada pela op. relevante pelo fato dessa representação muitas vezes ser da mesma ordem de complexidade do total de operações.

Somatórios simples:

1. soma de uma constante: 
   
   
2. soma dos nºs naturais até n: 

Exemplos:

1. análise da função fatorial

   int fatorial (int N) {       int fat = 1;       for (in i=2; i<=N; i++)          fat = fat * i;       return fat;    }

   Operação relevante: multiplicação f(n) = nº de repetições da OP. relevante

   
   
2. soma de matrizes
   
   

   for(int i=1; i<=N; i++)       for(int j=1; i<=N; j++)          C[i][j] = A[i][j] + B[i][j]

   Operação relevante: soma f(n) = nº de repetições da OP. relevante

   
   
3. multiplicação de matrizes
   
   

   for(int i=1; i<=N; i++)       for(int j=1; i<=N; j++){          C[i][j] = 0;          for(int k=1; k<=N; k++)             C[i][j] = C[i][j] + A[i][k] * B[k][j];       }

   Operação relevante: multiplicação f(n) = nº de repetições da OP. relevante

   
   
4. dois laços em sequência
   

   int soma = 0;    for(int i=1; i<=N; i++)       scanf("%d", &a[i]);    for(int j=1; i<=N; j++)       soma = soma + a[j];

   f(n) = nº de instruções