Hello everyone, it's my first time posting here and it's an urgent matter as I need the solution to this by midnight tonight :/

I'm really struggling with the all Big-Oh notation thing and I could really use your help.

I have this C++ code:

``````void Teste::listarMaisAfastados()
{
int maior = 0;
for (int i = 0; i <= utilizadores.NumVert(); i++)
{
for(int y = 0; y <= utilizadores.NumVert(); y++)
{
int tmp = utilizadores.distancia(tmpUL, TmpYL, false);
if(tmp > maior)
{
maior = tmp;
maiorX = tmpUL;
maiorY = TmpYL;
}
}
}
cout << endl << "A maior distancia encontrada foi entre os utilizadores: " << endl << endl;
cout << maiorX << endl;
cout << maiorY << endl;
cout << endl << "Distancia: " << maior << endl << endl;
}``````

What's the complexity of this? I think it's O(N^2) but I'm not sure..

## All 5 Replies

Post code for `utilizadores.getVerticeById()` , and `utilizadores.distancia()` .
If they are linear, then this function is of [TEX]O(n^{2})[/TEX] time complexity.

I think its safe to say utilizadores.getVerticeById() is linear at worst, but utilizadores.distancia() has to be constant time for this to be O(n^2) complexity.

getVerticeById

``````template<class TV,class TR>
{
Vertice<TV,TR>* v=graf;
Ramo<TV,TR>* r ;
int counter = 1;

if (v == NULL)
{
//cout << "Grafo nao definido !" << endl ;
}
else
{
while (v != NULL && counter <= id)
{
if (counter == id)
{
return v->vconteudo;
}
v=v->apvertice;
counter ++;
}
}
return v->vconteudo;
}``````

distancias

``````template <class TV, class TR>
int ListAdjGrafo<TV,TR>::distancia( TV& ini,  TV& fim, bool showErrors)
{
bool *processados = new bool[nvertices + 1];
for (int i = 1; i <= nvertices; i++)
{
}

int *caminho = new int [nvertices + 1];
for (int i = 1; i <= nvertices; i++)
{
caminho[i] = 0;
}

int *distancia = new int[nvertices + 1];
for (int i = 1; i <= nvertices; i++)
{
distancia[i] = 9999;
}

Vertice<TV, TR> *apvertini = encvert_conteudo(ini);
Vertice<TV, TR> *apvertfim = encvert_conteudo(fim);

if (apvertini == NULL || apvertfim == NULL)
{
return -1;
}

int indice_origem = apvertini->key;
distancia[indice_origem] = 0;

while (indice_origem != -1)
{
apvertini = encvert_key(indice_origem);
Ramo<TV, TR> *apramo = apvertini->apramo;
while (apramo != NULL)
{
int indice_destino = apramo->apv->key;
if (!processados[indice_destino] && distancia[indice_destino]>(distancia[indice_origem] + apramo->rconteudo))
{
distancia[indice_destino] = distancia[indice_origem] + apramo->rconteudo;
caminho[indice_destino] = indice_origem;

}
apramo = apramo->apr;
}
}

apvertini = encvert_conteudo(ini);
apvertfim = encvert_conteudo(fim);
if (distancia[apvertfim->key] == 9999)
{
if (showErrors) cout << "Nao existe caminho entre" << apvertini->vconteudo << " e " << apvertfim-> vconteudo << endl;
return -1;
}

return distancia[apvertfim->key];
}``````

Can someone explain this to me step by step? I searched it but I can never find an easy explanation.. :/

`getVerticeById` is clearly O(n).
The part below of `ListAdjGrafo<TV,TR>::distancia` seems to be of O(n^{2}) complexity because of the cascading while loops.
So this algorithm is at least O(n^{4}) complexity.
Final answer would depend on the complexity of `encvert_key` , `encvert_conteudo` and `distanciaMinimaVertice` What relation does `indice_origem` have with the inputs `ini` and `fim` ?

``````Vertice<TV, TR> *apvertini = encvert_conteudo(ini); // O(? )
Vertice<TV, TR> *apvertfim = encvert_conteudo(fim);// O(? )

int indice_origem = apvertini->key;
distancia[indice_origem] = 0;

while (indice_origem != -1){ //  O(n2) because of the inner while loop called by this while loop.
apvertini = encvert_key(indice_origem); // O(?)
Ramo<TV, TR> *apramo = apvertini->apramo;
while (apramo != NULL){
int indice_destino = apramo->apv->key;
if (!processados[indice_destino] && distancia[indice_destino]>(distancia[indice_origem] + apramo->rconteudo)){
distancia[indice_destino] = distancia[indice_origem] + apramo->rconteudo;
caminho[indice_destino] = indice_origem;
}
apramo = apramo->apr;
}