Complexity of this simple algorithm

Question

I did a algorithm to resolve a problem, but I don't know its complexity. The algorithm verifies if all of the vertex of a graph are "good". A "good" vertex is a vertex that can access all others vertexes of a graph following a path that started himself.

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);
}

Graph tested

Thanks and sorry for my english.

A method named addIfUnique taking an ArrayList<Character> suggests that you should be using a Set<Character> instead, and just calling add. — Andy Turner
– Andy Turner, Commented Jun 5, 2016 at 21:50
I think that this code will potentially loop infinitely if cycles exist in your graph. — Andy Turner
– Andy Turner, Commented Jun 5, 2016 at 21:54
Yes, the code can stay in loop infinitely, but on example, I have vertexes without edges, so it's a condition to stop — Lucas Moura
– Lucas Moura, Commented Jun 5, 2016 at 23:48

Simone C. · Accepted Answer · 2016-06-05 22:00:06Z

2

I think the complexity is O(n^2), because you use a nested loop by calling:

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

edited Jun 5, 2016 at 22:00

answered Jun 5, 2016 at 21:51

Simone C.

3694 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Andy Turner Over a year ago

So, the for loop in verify calling getChildren(), which contains a for loop - that's not a nested loop?

Simone C. Over a year ago

So do you think the asymptotic complexity would be O(n^2)?

Andy Turner Over a year ago

No, I'm not making any claims as to the correct complexity; I'm merely questioning "because you didn't use a nested loop".

Lucas Moura Over a year ago

So, the complexity of all code is O(n^2)? The method addIfUnique not influence the complexity?

Simone C. Over a year ago

The method addIfUnique has a for loop, but doesnt influnce because if we add the for loop to the nested, which would be O(n) + (n^2), the result would be O(2n^2), that is, asymptotically, O(n^2).

|

Collectives™ on Stack Overflow

Complexity of this simple algorithm

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related