How to calculate the time complexity?


  • 0
    S
      public int maxProfit(int[] prices) {
    	if (prices.length < 2) {
    		return 0;
    	}
    	return find(prices,prices.length-1);
     }
    
    public int find(int[] arr, int maxIdx) {
    	if (maxIdx < 1) {
    		return 0;
    	}
    	int min = arr[0];
    	int minIdx = 0;
    	for (int i = 1; i <= maxIdx; i++) {
    		if (arr[i] < min) {
    			min = arr[i];
    			minIdx = i;
    		}
    	}
    
    	// Find right max
    	int maxRight = 0;
    	for (int i = minIdx + 1; i <= maxIdx; i++) {
    		int tmp = arr[i] - min;
    		if (tmp > maxRight) {
    			maxRight = tmp;
    		}
    	}
    	int maxLeft = 0;
    	if (minIdx == 2) {
    		maxLeft = arr[1] - arr[0];
    	} else if (minIdx > 2) {
    		maxLeft = find(arr, minIdx - 1);
    	}
    
    	if (maxRight > maxLeft) {
    		return maxRight;
    	} else {
    		return maxLeft;
    	}
    }
    

    What is the time complexity of my solution? Is it N * Log (N). How to calculate that? Thank you.


  • -6
    Y

    isn't it O(N)? i don't see anything abnormal in your code. for calculation, focus on the for loop.


  • 0
    S

    No. The least cost is O(N),such as 1,2,3,....n , the worst is O(N*N), which is (n, n-1, n-2....1).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.