Enunciado:
Suponha que, para resolver um determinado problema, você desenvolveu um algoritmo que constrói um grafo onde cada vértice contém um dado de entrada e há uma aresta ligando um vértice x a um vértice y somente se uma determinada relação envolvendo os dois vértices é verificada. Note que o número de vértices é exatamente o tamanho "n" da entrada.
Considere ainda que o grafo contruído pelo seu algoritmo seja representado por uma matriz de adjacência e que você precisa encontrar as arestas existentes no seu grafo (as arestas não fazem parte dos dados de entrada!). Qual das alternativas abaixo certamente NÃO é um limite assintótico para a complexidade do seu algoritmo?

A) Theta(n)
B) Theta(n²)
C) Theta(n²lgn)
D) Theta(n³)
E) NDA

Autor: José Augusto Amgarten Quitzau