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