Answer to Question #148654 in Algorithms for shabab

Question

int myFunc(int A[], int n)
{
int i, j, max = 0;
int msis[n];

for ( i = 0; i < n; i++ )
msis[i] = A[i];

for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if (A[i] > A[j] &&
msis[i] < msis[j] + A[i])
msis[i] = msis[j] + A[i];

for ( i = 0; i < n; i++ )
if ( max < msis[i] )
max = msis[i];

return max;
}
a) What is the time complexity of the algorithm

Answer 1

Previous answer

a) What is the time complexity of the algorithm

First loop run n times

Second loop with inner loop run 1+2+...+n = n*(n+1)/2 times

third loop run n times

So

n + n*(n+1)/2 + n = n^2/2 + 5*n/2 = O(n^2)