I'm trying to find a way to optimize my algorithm such that the running time is O(n²) (Big O Notation).
The input is an array with n elements, of only positive and negative integers. We can assume that the array is already sorted.
I have to determine: for each r (element of the array), whether r = s + t, where s and t are also elements of the array, and can be the same (s == t), or also zero.
I tried to reduce the number of elements I have to check by checking if the current number is positive or negative, but the running time is still too long. The problem is that I'm using 3 while loops which already means a running time of O(n³) for the worst case.
Here is my code:
public static void Checker(int[] array) {
List<Integer> testlist = new ArrayList<Integer>();
int i = 0;
while (i < array.length) {
int current = array[i];
if (attached(current, array)) {
testlist.add(current);
}
i++;
}
}
public static boolean attached(int current, int[] array) {
boolean result = false;
int i = 0;
while (i < array.length && !result) {
int number1 = array[i];
int j = 0;
while (j < array.length && !result) {
int number2 = array[j];
if (number1 + number2 == current) {
result = true;
}
j++;
}
i++;
}
return result;
}
The two main measures for the efficiency of an algorithm are time complexity and space complexity, but they cannot be compared directly. So, time and space complexity is considered for algorithmic efficiency. An algorithm must be analyzed to determine the resource usage of the algorithm.
To calculate the running time, find the maximum number of nested loops that go through a significant portion of the input. Some algorithms use nested loops where the outer loop goes through an input n while the inner loop goes through a different input m. The time complexity in such cases is O(nm).
In this article, we learn how to estimate the running time of an algorithm looking at the source code without running the code on the computer. The estimated running time helps us to find the efficiency of the algorithm. Knowing the efficiency of the algorithm helps in the decision making process.
It's running time does not depend on value of n, like size of array or # of loops iteration. Independent of all these factors, it will always run for constant time like for example say 10 steps or 1 steps. Since it's performing constant amount of steps, there is no scope to improve it's performance or make it faster.
You can start sorting the array O(nlogn)
(if not), then for each element in the array you can check if there are two elements that the sum is equals to the number in O(n²)
.
The code is in C#:
public static bool Solve(int[] arr)
{
Array.Sort(arr); //If not already sorted
foreach (var num in arr)
if (!FindTwoThatSumN(arr, num))
return false;
return true;
}
public static bool FindTwoThatSumN(int[] arr, int num)
{
int min = 0;
int max = arr.Length - 1;
while (true)
{
if (min == max) break;
int sum = arr[min] + arr[max];
if (sum < num) min++;
if (sum > num) max--;
if (sum == num) return true;
}
return false;
}
The idea to check if there are two numbers in an array (must be sorted) that sum a specific value is start from the minimum (min = 0
) and the maximum (max = arr.Length
), then in each iteration:
min
index.max
index.min
index reach max
then there are no solution.You can refer to this question/answers for more details and proof.
Time complexity for overall solution is O(n²)
:
O(nlogn)
.O(n)
.O(n)
.So, is O(n²)
due the nested calls to FindTwoThatSumN
.
If you want you can pass the index instead of the number to FindTwoThatSumN
method to avoid with an additional check use the number itself as part of the solution.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With