Time Complexity/Big O of this algorithm

Time Complexity/Big O of this algorithm
0

#1

Hi all,

I came across a problem online and after finding a solution I noticed they said it can be solved with O(n) complexity.

The problem is:

Suppose we could access yesterday’s stock prices as an array, where:

The indices are the time in minutes past trade opening time, which was 9:30am local time.
The values are the price in dollars of Apple stock at that time.
So if the stock cost $500 at 10:30am, stockPricesYesterday[60] = 500.

So:

var stockPricesYesterday = [10, 7, 5, 8, 11, 9];

getMaxProfit(stockPricesYesterday);
// returns 6 (buying for $5 and selling for $11)

my solution is here:

var stockPricesYesterday = [10, 7, 5, 8, 11, 9];

function getMaxProfit(arr){

  if (arr.length === 1){
    return 'no profit options';
  }
  
  let min = Math.min.apply(null, arr);
  let max = Math.max.apply(null, arr);
  
  let indexMin = arr.indexOf(min);
  let indexMax = arr.indexOf(max);
  
  if ((Math.abs(indexMax - indexMin) >= 1) && indexMin < indexMax){
    return max - min;
  } else {
    arr.splice(indexMin, 1);
    return getMaxProfit(arr);
  }
}

getMaxProfit(stockPricesYesterday);

While I think this does solve the problem I am a bit confused determining the time complexity of the algorithm. My thinking is as follows:

Getting the min and max value in the array - these operations take N time
Getting the index of min and max value - these take N time worst case or are constant best case(if value is at index 0)?

Then we check if we have an answer and if so return the value O(1)?
If not, the min value is spliced out (N worst case?) and the function is called recursively. Worst case this happens N-1 times?

So my question if this function executes without recursing is it O(n) time complexity (it’s like 4N but we can ignore the 4 constant?)

And, if it DOES recurse does it become O(N^y) where Y is the number of times it recurses? I know that when you have 2 nested for loops for example the algorithm is N^2, so does this apply to recursive calls as well?

Thanks everyone


#2

Hi Swoodend,

You are right on your estimations of the time complexity at the various checkpoints of your algorithm and why they are that way, but there seems to be some confusion on how the term big o notation is used. When we talk about big O we mean worst case scenario of the entire algorithm as a whole in this case the recursive case, so for your algorithm O(N^x)where x is the length of the array. When you refer to your best case scenario we use Big omega notation for best case scenario(in your case OMEGA(1)), but it isn’t as widely used because in the real world we hardly ever get best case.

individual questions questions:

  • Getting the index of min and max value - these take N time worst case or are constant best case(if value is at index 0)?
  • I think they are O(n) but i'm not sure how java script libraries do it.
  • Then we check if we have an answer and if so return the value O(1)? If not, the min value is spliced out (N worst case?) and the function is called recursively. Worst case this happens N-1 times?
  • The time complexity cost of returning the value is 1 but again it would be improper to say O(1). If this case was the worst case it would still be O(n) because of the previous work
  • it’s like 4N but we can ignore the 4 constant??
  • Yup. it becomes negligible when we scale up.
  • And, if it DOES recurse does it become O(N^y) where Y is the number of times it recurses?
  • Yea, I think that it's O(N^N) a little closer to O(N!), but we do shorten that to O(N^x)

To find the O(n) solution try to do work while iterating over the array in a for loop. Let me know if you want the psudo code.

Hope this helped


#3

Hi @TitoTaquito,

So I’ve written another version of this alg, which I think is O(n):

let stockPricesYesterday = [10, 9, 15,6, 30];

function getMaxProfit(arr){
  //index is #mins past 9:30AM
  
  let min = 0;
  let max = 0;
  let maxIndex;
  let minIndex;
  let profitOptions = [];
  
  for (let i = 0; i < arr.length; i++){
    let price = arr[i];

    if (!min && !max){
      min = price;
      max = price;
      minIndex = i;
      maxIndex = i;
    } else {
      if (price < min){
        min = price;
        minIndex = i;
      }
      
      if (price > max){
        max = price;
        maxIndex = i;
      }
      
      //if index is after max index, and price is lower than max, return min-max as this represents a loss
      if (i > maxIndex && (price < max)){
        profitOptions.push(min - max);
      } else {
        profitOptions.push(max - min);
      }
      
      
    }
  }
    
   return profitOptions.reduce((max, val) => {
     return val > max ? val : max;
   }, 0);
}

getMaxProfit(stockPricesYesterday);

In this case at the start we declare and assign some varaibles - O(1)
Then we iterate over the array of stock prices - O(n)
Some conditional assignment is performed -O(1)
Finally, after the loop finishes we return the largest value in the profitOptions array via reduce - O(n)

So we have 2N + some constant work = O(n) algorithm overall.

Does this sound right?

Thanks very much for your help and insight


#4

Exactaly! Nice work.