Help with Big-Oh

[Ty88]

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;
	Utilizador maiorX, maiorY;
	for (int i = 0; i <= utilizadores.NumVert(); i++)
	{
		Utilizador tmpUL = utilizadores.getVerticeById(i);
		for(int y = 0; y <= utilizadores.NumVert(); y++)
		{
			Utilizador TmpYL = utilizadores.getVerticeById(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..

Thanks in advance

[WolfPack]

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

[sixstringartist]

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.

[Ty88]

getVerticeById

template<class TV,class TR>
TV ListAdjGrafo<TV,TR>::getVerticeById(int id) const
{
	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++)
	{
        processados[i] = false;
	}

    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) 
	{
        processados[indice_origem] = true;
        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;
        }	
        indice_origem = distanciaMinimaVertice(distancia, processados);		
    }
	
    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.. :/

[WolfPack]

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.
        processados[indice_origem] = true;
        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;
        }	
        indice_origem = distanciaMinimaVertice(distancia, processados);	//O(?)	
    }

It is a bit difficult to explain unless I write a tutorial on O-notation which I am incapable and not interested in doing.
Also there are a lot of tutorials out there, so if you have read them, it is just a matter of learning how to apply them which I can't teach you anyway. here is one.

[Ty88]

thanks for your help and quick responses. Thanks to the last response I could finally undertand it. :)