CODEWITHSUNDEEP
algorithm
Joe
Joe

Reputation: 381

How to calculate time complexity of DFS algorithm?

Like the function below, how to calculate its time complexity? I think it's should be O(m*n)...

int uniquePaths(int m, int n) {
    if (m < 1 || n < 1) return 0;     
    if (m == 1 && n == 1) return 1;      
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}

Upvotes: 2

Views: 292

Answers (2)

displayName
displayName

Reputation: 14379

The Recursion Tree:

To represent a problem with m = M and n = N, let's write it as <M, N>. If we try to draw the recursion tree of this problem:

  • At root, we have one problem: <M, N>
  • Then, root breaks to two problems: <M-1, N> and <M, N-1>
  • And, if we continue down this recursion tree, we will reach to leaves, which will be <0, 0>.

Tree's Depth:

But, what is the maximum depth possible for this tree? It's 1(M + N). Further, each node <M, N> can break to at most 2 paths, viz. <M-1, N> and <M, N-1>.

Inferring Complexity From Tree:

So, what is the maximum number of leaves possible? (Hint: 2(M + N))

Well, since every node breaks to two nodes, at every level, the number of leaves will be multiplied by 2, starting from 1 at the root.

  • So, starting from root, total leaves possible = 2(M + N - 1).
  • Multiplying and dividing by 2 gives us, (1 / 2) * 2(M + N)
  • Getting rid of the constant value (1 / 2) gives us the complexity = 2(M + N) !

Hence, the complexity of your algorithm can be upper bounded to O(2(m + n)).

1The longest path will start from <M, N> and first go to <0, N>. Then from there it will go to <0, 0>. So, longest possible path length = M + N.

Upvotes: 1

blazs
blazs

Reputation: 4845

You can model the time complexity with the recursive function T(m,n) = T(m-1, n) + T(m, n-1), where T(1,1)=1 and T(m,n)=0 whenever min(m,n)<1.

It looks like T(m,n)=(m+n choose m). To see this note that (m+n choose n) = (m+n-1 choose m) + (m+n-1 choose m-1) by the recurrence for the binomial coefficients, and that T(m,n) = T(m-1, n) + T(m,n-1) is exactly the same recurrence.

Thus T(m,n) = O((m+n)^n / n!). (There are many other bounds.)

Upvotes: 2

Related Questions