JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (oldest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Re: Example 3 (response to post by misof) | Reply
I have a small doubt regarding the while loop, and how it's executed at most N times. I agree that
j++
is executed at most N times, but what about the conditions inside while loop?

I am talking about
while(j<N-1) && (A[i]-A[j] > D)
those comparisons are surely made at most N2 times right? Why are we not counting them?

This must be something basic, but I don't know.
Re: Example 3 (response to post by jchaganti) | Reply
The introduction to that example says: "Given is a sorted array A."
The array is supposed to be sorted in ascending (increasing) order.
Example 3 | Reply
Please refer to the example 3 having following code:

int j=0;
for (int i=0; i<N; i++) {
while ( (j><N-1) && (A[i]-A[j] > D) )
j++;
if (A[i]-A[j] == D) return 1;
}

This would fail if the input integer array has following values and D =1 :

10, 5, 4, 2

I feel there is a problem with the way j is incremented.

Am i missing something??

Thanks
RSS