How do I calculate this code's time complexity?

Question

I'm struggling with calculating time complexity in this code. Only capable of simple code at the moment... just want to try with complex one!

public static int PATHWAY = 0;
public static int WALL = 1;
public static int MARKED = 2;

public static boolean find(int x, int y) {
    if(x == 7 && y == 7) return true;
    maze[x][y] = MARKED;
    if(x != 0 && maze[x-1][y] == PATHWAY && find(x-1, y)) return true;
    if(y != 0 && maze[x][y-1] == PATHWAY && find(x, y-1)) return true;
    if(x != 7 && maze[x+1][y] == PATHWAY && find(x+1, y)) return true;
    if(y != 7 && maze[x][y+1] == PATHWAY && find(x, y+1)) return true;
    return false;
}

Am I wrong or it could never converge? – Christian Vincenzo Traina Oct 04 '19 at 07:25 — Christian Vincenzo Traina, Oct 04 '19 at 07:25

score 0 · Answer 1 · answered Oct 04 '19 at 07:14

Basically you can calculate assignments and operations. Have a

int assignments = 0;
int operations = 0;

which you will increment every time you do one.

Other way in doing this is to monitor the time, but it's not the most reliable one.

You can also calculate/approximate Big-O, check Big O, how do you calculate/approximate it?

score 0 · Accepted Answer · answered Oct 04 '19 at 07:15

Well, in each recursive call you visit a single cell in your 2D array.

Since you mark the visited cells, you can't visit the same cell twice.

Hence the total recursive calls is bound by the length of the 2D array.

Apart from the recursive call, you perform a constant amount of work in each execution of the find() method.

Therefore the time complexity is O(N*M) if N is the number of rows and M the number of columns of the 2D array.

Of course, based on your stopping condition of if(x == 7 && y == 7) return true;, it looks like the dimensions of your 2D array are 8x8, which can be seen as a constant. That would make the running time O(1).

O(N*M) is the complexity for a general input array.

score 0 · Answer 3 · answered Oct 04 '19 at 07:31

Well it's not that hard, it actually uses DFS in order to find a path. the order of DFS is O(V+E), where V is the number of vertices and E is the number of edges.

In this case you are using a adjacency matrix to represent your graph. so in worst case the time complexity would be O(M*N), where M is the number of rows and N is the number of columns.

How do I calculate this code's time complexity?

3 Answers3