Finding time complexity of recursive function

Question

I'm trying to find the overall time complexity of this function using Big-Oh notation, The function checkElements() is invoked recursively which resides insides of the percolates().Any help here is very much appreciated

public static boolean percolates(boolean[][] open) {
    size = open.length;
    uf = new WeightedQuickUnionUF((size * size) + 2);
    for (int i = 0; i < open.length; i++) {//connect all top row elements to virtual top node.
        uf.union(0, i);
    }

    for (int j = 0; j < open.length; j++) {//connect all bottom row elements to bottom virtual node
        uf.union((size * size) + 1, (size * size) - j);

    }
    int row = 0; // current row of grid
    int column = 0;// current column of grid
    int ufid = 1; // current id of union find array
    checkElements(column, row, open, ufid);
    boolean systemPerculates = uf.connected(0, (size * size) + 1);
    System.out.println("Does the system percoloates :" + systemPerculates);
    return systemPerculates;
}

//search elements in the grid
public static void checkElements(int column, int row, boolean open[][], int ufid) {
    if (open[row][column]) {
        if (column - 1 >= 0 && open[row][column - 1]) { //check adjacent left
            uf.union(ufid, ufid - 1);

        }
        if (column + 1 < size && open[row][column + 1]) {//check adjacent right
            uf.union(ufid, ufid + 1);

        }
        if (row - 1 >= 0 && open[row - 1][column]) {//check adjacent top
            uf.union(ufid, ufid - size);

        }
        if (row + 1 < size && open[row + 1][column]) {//check adjacent bottom
            uf.union(ufid, ufid + size);

        }
    }
    if (column + 1 < size) {      //go to next column
        ufid++;
        column++;
        checkElements(column, row, open, ufid);
    } else if (column + 1 == size && row + 1 < open.length) {  //go to next row 
        ufid++;
        row++;
        column = 0;
        checkElements(column, row, open, ufid);
    } else {
        return;
    }

}

Where is the recursion?

Stefan Haustein
– Stefan Haustein

2016-04-22 08:57:08 +00:00
Commented Apr 22, 2016 at 8:57 — Stefan Haustein
– Stefan Haustein, Commented Apr 22, 2016 at 8:57
the method checkElements()

TheLoneWolf91193
– TheLoneWolf91193

2016-04-22 11:18:12 +00:00
Commented Apr 22, 2016 at 11:18 — TheLoneWolf91193
– TheLoneWolf91193, Commented Apr 22, 2016 at 11:18

Stefan Haustein · Accepted Answer · 2016-04-22 11:33:20Z

This might be easier to follow if you change the recursive calls to

if (column + 1 < size) {      //go to next column
    checkElements(column + 1, row, open, ufid + 1);
} else if (column + 1 == size && row + 1 < open.length) {  //go to next row 
    checkElements(0, row + 1, open, ufid + 1);
} else {
    return;
}

You are doing only up to one recursive call in checkElements, and each call seems to reduce the considered input by one, and you only do a constant amount of processing at each step, so the runtime should just be O(n).

While this seems to be easy to calculate, linear recursion depth is usually not a good idea (other than in languages that recognize and support tail recursion) because stack size is usually much more limited than heap space -- you may easily run into a stack overflow exception.

So typically, one would just have two nested loops (for rows and columns), unless I miss something important wrt. the processing going on in your code.

also how may I find the lower bound or big theta for the same code?
I think it's all the same bound -- there doesn't seem to be any special input that would shorten the runtime -- all cells seem to be traversed in any case.

Collectives™ on Stack Overflow

Finding time complexity of recursive function

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related