I'm given this method, and requested to analyze what it does, and minimize its complexity (both time and space).
All values are known to be larger than zero.
public static boolean search(int[] a, int num) {
for(int i = 0; i < a.length; i++)
for(int j = i; j < a.length; j++) {
int res = 0;
for(int k = i; k <= j; k++)
res += a[k];
if(res == num)
return true;
}
return false;
}
From what it looks to me it's searching for any series of consecutive numbers in the given array, that sum up to num
, with an O(n3) complexity.
I've tried to rewrite it like this:
public static boolean search(int[] a, int num) {
for (int i = 0; i < a.length; i++) {
int sum = 0;
for (int j = i; j < a.length; j++) {
sum += a[j];
if (sum == num)
return true;
}
if (num > sum)
break;
}
return false;
}
Which has a complexity of (BTW, is there a better way to denote this complexity?).
What other strategies can I take to minimize the complexity even further? Can I reach O(n)?
+1
part after multiplying \$\endgroup\$ – RobAu Jan 14 at 8:26