Сложность этого простого алгоритма

Question

Я сделал алгоритм для решения проблемы, но я не знаю его сложности. Алгоритм проверяет, являются ли все вершины графа "хорошими". "Хорошая" вершина - это вершина, которая может получить доступ ко всем остальным вершинам графа по пути, который начался сам.

public static boolean verify(Graph graph)
{
    for(int i=0; i < graph.getVertex().size(); i++)
    {
        // List of vertexes visited 
        ArrayList<Character> accessibleVertex = new ArrayList<Character>();
        getChildren(graph.getVertex().get(i), graph.getVertex().get(i).getName(), accessibleVertex);    

        // If the count of vertex without father equals a count of the list of vertexes visited, his is a "good" vertex
        if((graph.getVertex().size()-1) == accessibleVertex.size())
            return true;
    }

    return false;
}

private static void getChildren(Vertex vertex, char fatherName, ArrayList<Character> accessibleVertex)
{
    // Ignore the 'father'
    if(vertex.getName() != fatherName)
        addIfUnique(vertex.getName(), accessibleVertex);

    for(int i=0; i < vertex.getEdges().size(); i++)
    {
        getChildren(vertex.getEdges().get(i).otherVertex(), fatherName, accessibleVertex);
    }
}

private static void addIfUnique(char name, ArrayList<Character> accessibleVertex)
{
    boolean uniqueVertex = true;

    for(int i=0; i < accessibleVertex.size(); i++)
    {
        if(accessibleVertex.get(i).equals(name))
            uniqueVertex = false;
    }

    if(uniqueVertex)
        accessibleVertex.add(name);
}

График проверен

Спасибо и извините за мой английский.

Answer 1

Я думаю, что сложность O(n^2), потому что вы используете вложенный цикл, вызывая:

getChildren(graph.getVertex().get(i), graph.getVertex().get(i).getName(), accessibleVertex);