0

Given a list of N integers, the 3-sum problem is to determine whether there exists 3 integers in the list (not necessarily distinct) such that x + y + z = 0. Suppose that you are executing the brute force algorithm below on a computer that executes 1 billion operations (addition, increment, or comparison) per second. int brute
int brute(int a[], int N)
{
int i, j, k;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
for (k = 0; k < N; k++)
if (a + a[j] + a[k] == 0) return 1;
return 0; // none found
}
Estimate how many seconds it will take (in the worst case) to solve a problem of size N = 1,000?

2
Contributors
1
Reply
2
Views
11 Years
Discussion Span
Last Post by Rashakil Fol
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.