Complexity of a recursive algorithm

Question

I'm doing a project. I need to calculate the complexity of a recursive method. This method is called recursively and uses methods "incomingEdges" and "opposite". Can someone help me to find the complexity of "FUNCTION" method?

public HashMap<String, Integer[]> FUNCTION() {

    HashMap<String, Integer[]> times = new HashMap<>();
    Integer[] timesAct = new Integer[5];
    boolean[] visited = new boolean[graphPertCpm.numVertices()];

    Vertex<Activity, String> current = graphPertCpm.getVertex(0);
    timesAct[0] = 0;
    timesAct[1] = 0;
    times.put(current.getElement().getKeyId(), timesAct);
    FUNCTION(current, times, visited);

    return times;
}

private void FUNCTION(Vertex<Activity, String> current, HashMap<String, Integer[]> times, boolean[] visited) {

    if (times.get(current.getElement().getKeyId()) == null) {
        for (Edge<Activity, String> inc : graphPertCpm.incomingEdges(current)) {
            Vertex<Activity, String> vAdj = graphPertCpm.opposite(current, inc);
            FUNCTION(vAdj, times, visited);

        }
    }

    visited[current.getKey()] = true;
    for (Entry<Vertex<Activity, String>, Edge<Activity, String>> outs : current.getOutgoing().entrySet()) {
        if (!visited[outs.getKey().getKey()]) {
            int maxEF = 0;
            Vertex<Activity, String> vAdj = graphPertCpm.opposite(current, outs.getValue());
            for (Edge<Activity, String> inc : graphPertCpm.incomingEdges(outs.getKey())) {
                Integer[] timesAct = times.get(graphPertCpm.opposite(outs.getKey(), inc).getElement().getKeyId());
                if (timesAct == null) {
                    vAdj = graphPertCpm.opposite(vAdj, inc);
                    FUNCTION(vAdj, times, visited);
                } else {
                    if (timesAct[1] > maxEF) {
                        maxEF = timesAct[1];
                    }
                }
            }
            Integer[] timesAct = new Integer[5];
            timesAct[0] = maxEF;
            timesAct[1] = timesAct[0] + outs.getKey().getElement().getDuration();
            times.put(outs.getKey().getElement().getKeyId(), timesAct);
            if (visited[vAdj.getKey()] != true) {
                FUNCTION(vAdj, times, visited);
            }
        }
    }

    visited[current.getKey()] = false;
}

Opposite Method

  public Vertex<V, E> opposite(Vertex<V, E> vert, Edge<V, E> e) {

    if (e.getVDest() == vert) {
        return e.getVOrig();
    } else if (e.getVOrig() == vert) {
        return e.getVDest();
    }

    return null;
}

IncomingEdges Method

    public Iterable<Edge<V, E>> incomingEdges(Vertex<V, E> v) {

    Edge e;
    ArrayList<Edge<V, E>> edges = new ArrayList<>();

        for (int i = 0; i < numVert; i++) {
            for (int j = 0; j < numVert; j++) {
                e = getEdge(getVertex(i), getVertex(j));
                if (e != null && e.getVDest() == v) {
                    edges.add(e);

                }
            }
        }


    return edges;
}

You've dumped quite a bit of code here, and few SO users will do a formal analysis. I would recommend that you add logging statements to the various portions of each recursive call and then compare this output for different inputs. You can build a graph this way empircally. — Tim Biegeleisen
– Tim Biegeleisen, Commented Nov 9, 2015 at 12:27

Michael Queue · Accepted Answer · 2015-11-11 01:44:01Z

So, first are you familiar with the concepts of Big-O analysis?

The most common metric for calculating time complexity is Big O notation. This removes all constant factors so that the running time can be estimated in relation to N as N approaches infinity. In general you can think of it like this:

Constant O(1)

                                    statement;

The running time of the statement will not change in relation to N.

Linear O(n)

                        for ( i = 0; i < N; i++ )
                            statement;

The running time of the loop is directly proportional to N. When N doubles, so does the running time.

Quadratic O(n2)

                       for ( i = 0; i < N; i++ ) {
                            for ( j = 0; j < N; j++ )
                                statement;
                        }

The running time of the two loops is proportional to the square of N. When N doubles, the running time increases by N * N.

Logarithmic O(log n)

while ( low <= high ) {
  mid = ( low + high ) / 2;
if ( target < list[mid] )
  high = mid - 1;
else if ( target > list[mid] )
  low = mid + 1;
else break;
}

The running time of the algorithm is proportional to the number of times N can be divided by 2. This is because the algorithm divides the working area in half with each iteration.

Linearithmic O(n log n)

                       void quicksort ( int list[], int left, int right ){
                            int pivot = partition ( list, left, right );
                            quicksort ( list, left, pivot - 1 );
                            quicksort ( list, pivot + 1, right );
                        }

Is N * log ( N ). The running time consists of N loops (iterative or recursive) that are logarithmic, thus the algorithm is a combination of linear and logarithmic (also termed linearithmic).

Note that none of this has taken into account best, average, and worst case measures. Each would have its own Big O notation. Also note that this is a VERY simplistic explanation. Big O is the most common, but it's also more complex that I've shown. There are also other notations such as big omega, little o, and big theta. You probably won't encounter them outside of an algorithm analysis course.

Your function can be stripped down to two for-loops with recursive calls and one additional for-loop:

 for (Edge<Activity, String> inc : graphPertCpm.incomingEdges(current)) {
            Vertex<Activity, String> vAdj = graphPertCpm.opposite(current, inc);
            FUNCTION(vAdj, times, visited);

for (Entry<Vertex<Activity, String>, Edge<Activity, String>> outs : current.getOutgoing().entrySet()) {

        for (Edge<Activity, String> inc : graphPertCpm.incomingEdges(outs.getKey())) {

                FUNCTION(vAdj, times, visited);

Then as suggested, consult the Master Theorem

If you need complexity of Graph Operations, Looking at the Big-O Cheat Sheet yields

Collectives™ on Stack Overflow

Complexity of a recursive algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related