Time complexity of recursive call inside 2 for loops

Viewed 193

int maxProfit(int price[], int start, int end) 
{ 
  
    // If the stocks can't be bought 
    if (end <= start) 
        return 0; 
  
    // Initialise the profit 
    int profit = 0; 
  
    // The day at which the stock 
    // must be bought 
    for (int i = start; i < end; i++) { 
  
        // The day at which the 
        // stock must be sold 
        for (int j = i + 1; j <= end; j++) { 
  
            // If byuing the stock at ith day and 
            // selling it at jth day is profitable 
            if (price[j] > price[i]) { 
  
                // Update the current profit 
                int curr_profit = price[j] - price[i] 
                                  + maxProfit(price, start, i - 1) 
                                  + maxProfit(price, j + 1, end); 
  
                // Update the maximum profit so far 
                profit = max(profit, curr_profit); 
            } 
        } 
    } 
    return profit; 
} 

What is the time complexity of maxProfit ?

According to me, recurrence relation is :

T(0,n) = n^2*(T(0,i) +  T(j,n))

After this, How to solve this 2 variable recurrence relation ?

1 Answers

nested loop means n2 and if you calculate the two recursive equation then you find:

  1. the first recursive relation if n = 5 then it's gonna run 1,2,3,4 times. So, T(n) = T(1)+T(2)+T(3)+....+T(n-1)
  2. the second recursive relation if n = 5 then it's gonna run 4,3,2,1 times. So, T(n) = T(n-1)+T(n-2)+.....+T(1)

so T(n) = n2{ T(n-1)+T(n-1) } = n2{ 2T(n-1)} for {2T(n-1)} the complexity is O(2n) and now multiply it by n2 but since n2 is much smaller than 2n so we ignore them and complexity stands: O(2n)

Related