the code is supposed to find the maximal drop (or difference) between 2 numbers while the bigger number must come before the smaller one (not necessaraly one next to the other).
I was wondering if you could help me out here to understand the complexity of the code. What confuses me in this situation is, thinking of the worst case scenario ( correct me if I'm wrong please) I run through the array, n times for j and n-1 times for i. is it added up or multiplied? and why?
O(n+n-1)? or O(n*(n-1))?
public static int maximalDrop (int[] a)
{
int max=0; int i=0; int j=1;
while (j<a.length && i<a.length-1)
{
if (a[i] > a[j])
{
int temp = a[i] - a[j];
if (temp > max)
{
max = temp;
}
}
j++;
if (j>a.length-1)
{
i++;
j=i+1;
}
}
return max;
}
The complexity of this code is O(n * (n - 1) / 2) or O(n^2). The reasoning is simple, just consider the case where n = 4, then (i, j) values in the beginning of each iterations of while loop is as follows:
(0, 1), (0, 2), (0, 3)
(1, 2), (1, 3)
(2, 3)
It can be seen that the complexity is O(n * (n - 1) / 2) as i is incremented only when j loops from i + 1 to a.length.