449 views
0 votes
0 votes
Given a two dimensional array A with n rows and k columns initialized to -1 . what is the time complexity of the function f(A,m,m)?

int f(int **a,int n,int k)

{

     if ((n<=k)||(k<=1)) return 1;

    if(a[n][k]==-1)

         a[n][k]=f(a,n-1,k)+f(a,n-1,k-1);

  return a[n][k];

}

a)theta(m)

b)theta(m^2)

c)theta(2^m)

d)O(1)

}

2 Answers

1 votes
1 votes
Answer shoud be O(1), because here n and k both are equal.

But if the first 'IF' statement is at the bottom then its gonna take theta(m^2) rime evaluate the matrix.

Related questions