CODEWITHSUNDEEP
algorithmtime-complexity
user2038560
user2038560

Reputation: 137

What is the time complexity of a function with two parameters?

What is the time complexity of the following method? Two parameters give me lots of confusion. Thanks in advance. 

public int count(int m, int n) {
    if(m == 1 || n == 1) return 1;
    return count(m-1, n) + count(m, n-1);
}

Upvotes: 4

Views: 985

Answers (1)

amit
amit

Reputation: 178491

This is in O(2^(n+m)).

It can be proven using induction, where the induction step is:

T(n,m) = T(n-1,m) + T(n, m-1) =(*) 2^(n+m-1) + 2^(n+m-1) = 2*2^(n+m-1) = 2^(n+m)

Where (*) is the induciton hypothesis.

Upvotes: 3

Related Questions