Time complexity of the following code? | Hashnode

Thread

Aakash Mallik

S/W Engineer @ Samsung R&D Delhi

Jul 18, 2018

Time complexity of the following code?

int findMinPath(vector<vector<int> > &V, int r, int c) {   
    int R = V.size();   
    int C = V[0].size();   
    if (r >= R || c >= C) return 100000000; // Infinity   
    if (r == R - 1 && c == C - 1) return 0;   
    return V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1));   
}

#general-advice

Responses(1)

Mark

formerly known as M

Jul 18, 2018

I'm not great at this, but I'd guess

2^min(R, C) = min(2^R, 2^C)

Also known as "not great"

If you'd add memoization

R * C

Search Hashnode

Time complexity of the following code?

Responses(1)

Recent threads