Discuss O(n) algorithm in the C/C++ Help forum on Dev Articles. O(n) algorithm C/C++ Help forum discussing building and maintaining applications in C/C++. Find out why these languages are the foundation on which other languages are built.
Posts: 9
Time spent in forums: 2 m 37 sec
Reputation Power: 0
O(n) algorithm
Hi all,
I am supposed to design an O(n) algorithm that solves the following problem.
Input: An integer v and 2 sorted arrays A and B, each having n integers. Output: Yes if and only if there exist i and j such that v = A[i] + B[j].
No if no such i and j exist.
The algorithms I came up with were linear search, which gave O(n^2) and binary search, which gave O(n log n). None gave me an O(n) algorithm.
Posts: 995
Time spent in forums: 6 Days 13 h 57 m 35 sec
Reputation Power: 5
Nice assignment....
Must say I was stuck here too, but my roommate, who's a bit better at the O(x) stuff came up with this:
cpp Code:
Original
- cpp Code
int can_value_be_made(int value, int N, int a[], int b[])
{
int i, j, sum;
i = 0;
j = N - 1;
while((i != N) && ( j >= 0))
{
sum = a[i] + b[j];
if( sum == value)
{
return1;
}
else
{
if(sum < value)
i++;
else
j--;
}
}
return0;
}
In the worst case scenario (value can not be made), this takes 2n operations, which still classifies as O(n).
__________________ This is my code. Is it not nifty?
"The biggest problem encountered while trying to design a system that was completely foolproof, was, that people tended to underestimate the ingenuity of complete fools."
---Douglas Adams
Dev Articles Community Forums Sponsor:
September 28th, 2005, 09:59 PM
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
