Complexity analysis

[ShatteredPsycho]

I am trying to figure out what is the complexity of this method but I am not quite sure how to go about it. Since I have this functions who calls many more, not sure if I have to add, multiply or what to do

 

double FTotal = Operations.minimumCostHeavy(grafo, s1, s2, pathC, mapa, grafo, p1);

public static double minimumCostHeavy(AdjacencyMatrixGraph<Local, Estrada> map, Local from, Local to, LinkedList<Local> path, Graph<Personagem, Double> mapa, AdjacencyMatrixGraph<Local, Estrada> grafo, Personagem p) {
        if (!map.checkVertex(from) || !map.checkVertex(to)) {
            return -1;
        }
        path.clear();
        return minimumCostPath2(map, from, to, path, mapa, grafo, p);
    }

static <V> double minimumCostPath2(AdjacencyMatrixGraph<V, Estrada> graph, V source, V dest, LinkedList<V> path, Graph<Personagem, Double> mapa, AdjacencyMatrixGraph<Local, Estrada> grafo, Personagem p) {

        AdjacencyMatrixGraph<V, Double> graphDouble = new AdjacencyMatrixGraph();

        for (V v : graph.vertices()) {
            graphDouble.insertVertex(v);        // O(n)
        }
        for (int i = 0; i < 3; i++) {                   //O(n^2)
            for (int j = 0; j < graph.numVertices; j++) {
                boolean flag = false;
                if (graph.privateGet(i, j) != null) {
                    if (flag == false && (grafo.vertices.get(j).dono.equals(p.nomePersonagem))) {
                        graphDouble.insertEdge(graph.vertices.get(i), graph.vertices.get(j), (double) grafo.privateGet(i, j).pontosEstrada);
                        flag = true;
                    }
                    if (flag == false && (!"".equals(grafo.vertices.get(j).dono))) {
                        int n = getPersonna(mapa, grafo.vertices.get(j).dono).pontosPersonagem;
                        graphDouble.insertEdge(graph.vertices.get(i), graph.vertices.get(j), (double) grafo.privateGet(i, j).pontosEstrada + grafo.vertices.get(j).pontosLocal + n);
                        flag = true;
                    }
                    if (flag == false && "".equals(grafo.vertices.get(j).dono)) {
                        graphDouble.insertEdge(graph.vertices.get(i), graph.vertices.get(j), (double) grafo.privateGet(i, j).pontosEstrada + grafo.vertices.get(i).pontosLocal);
                        flag = true;
                    }
                    if (flag == false) {
                        graphDouble.insertEdge(graph.vertices.get(i), graph.vertices.get(j), (double) grafo.privateGet(i, j).pontosEstrada + grafo.vertices.get(i).pontosLocal);
                    }
                }
            }
        }
        return EdgeAsDoubleGraphAlgorithms.shortestPathHeavy(graphDouble, source, dest, path, p.pontosPersonagem);
    }

public static <V> double shortestPathHeavy(AdjacencyMatrixGraph<V, Double> graph, V source, V dest, LinkedList<V> path, int pPersonagem) {
        path.clear();
        if (graph.checkVertex(source) && graph.checkVertex(dest)) {     //1
            if (source.equals(dest)) {                                  //1
                path.add(source);
                return 0;
            }
            int verticesIndex[] = new int[graph.vertices.size()];
            shortestPathHeavy(graph, graph.vertices.indexOf(source), new boolean[graph.vertices.size()], verticesIndex, new double[graph.vertices.size()], pPersonagem);

            if (verticesIndex[graph.toIndex(dest)] != -1) {
                recreatePath(graph, graph.vertices.indexOf(source), graph.vertices.indexOf(dest), verticesIndex, path);
                path = revPath(path);
                double distance = 0;
                for (int i = 1; i < path.size(); i++) {                     //O(n)
                    distance += graph.getEdge(path.get(i - 1), path.get(i));
                }
                return distance;
            }
            return -1;
        }
        return -1;
    }

private static <V> void shortestPathHeavy(AdjacencyMatrixGraph<V, Double> graph, int sourceIdx, boolean[] knownVertices, int[] verticesIndex, double[] minDist, int pPersonagem) {
        for (int i = 0; i < graph.vertices.size(); i++) {       //O(n)
            minDist[i] = Double.MAX_VALUE;
            verticesIndex[i] = -1;
            knownVertices[i] = false;
        }
        int vOrig = sourceIdx;
        minDist[vOrig] = 0;
        while (vOrig != -1) {
            knownVertices[vOrig] = true;
            V vertex = graph.vertices.get(vOrig);
            for (V v : graph.directConnections(vertex)) {           //O(n*n)=O(n^2)
                int vAdj = graph.toIndex(v);
                if (!knownVertices[vAdj] && minDist[vAdj] > minDist[vOrig] + graph.getEdge(v, vertex) && pPersonagem >= graph.getEdge(v, vertex)) {
                    minDist[vAdj] = minDist[vOrig] + graph.getEdge(v, vertex);
                    verticesIndex[vAdj] = vOrig;
                }
            }
            vOrig = getVertMinDist(minDist, knownVertices);
        }
    }

 

private static <V, E> int getVertMinDist(double[] dist, boolean[] visited) {
        int vertMinDist = -1;
        double distance = Double.MAX_VALUE;

        for (int i = 0; i < visited.length; i++) {      //O(n)
            if (!visited[i] && dist[i] < distance) {
                distance = dist[i];
                vertMinDist = i;
            }
        }

        return vertMinDist;
    }

recreate path is linear

 

The rest I am not sure how to go about it

[colonel_mortis]

You just need to work through it backwards. You've got that getVertMinDist is O(n), so (void) shortestPathHeavy is O(n²) (max of n, n and n²). You then feed that into (double) shortestPathHeavy, and while you've not posted recreatePath I assume it's no worse than O(n), so that method is O(n²) too, and just keep working backwards from there. I've not worked through it properly but it looks like it will come out at O(n²).

[ShatteredPsycho]

10 hours ago, Erik Sieghart said:

What kind of complexity are you looking for?

If it's for a practical purpose there's no point in evaluating complexity. There is inefficiency though.

I had to have it written for a school project, but I think I managed to get it right

Where do you see the inefficiency?

4 hours ago, colonel_mortis said:

You just need to work through it backwards. You've got that getVertMinDist is O(n), so (void) shortestPathHeavy is O(n²) (max of n, n and n²). You then feed that into (double) shortestPathHeavy, and while you've not posted recreatePath I assume it's no worse than O(n), so that method is O(n²) too, and just keep working backwards from there. I've not worked through it properly but it looks like it will come out at O(n²).

Yeh I understood it. I was ignoring the fact that it was for the cycles. Before I was thinking that it incremented or scaled with the different calls

Thx for replying

[ono]

I seem to recall complexity analysis of graph algorithms being functions of both the number of vertices and edges. I only see references to n here, which seems to be the number of vertices. Clearly, I haven't actually read any of the code haha

23 hours ago, Erik Sieghart said:

You also have the big O wrong for the nested loop. The actual big O is 3n because you only do the outer loop a maximum of three times.

I haven't done this stuff in a long, long time, but aren't multiplicative constants irrelevant? O(3n) = O(n)