Complexity problem

[shila80]

Hello i'm new in java and i'm sorry if my english is not very good

i have a question to solve and i cann't figure it out how to solve it

i have this class

public class B
 {
   public boolean what(int []arr1,int[] arr2,int num)
    {
      for (int i=0;i<arr1.length;i++)
        for(int j=0;j<arr2.length;j++) 
            if (arr1[i]+arr2[j]==num)
               return true;
       return false;
  }
}    

the two arrays contains int
they are sorted from the smallest to the biggest numbers

i need to write another class with the same mathod
but in more efficient complexity (i think i need to do this in O(nlogn)beacuse here the complexity is n^2)

[iamthwee]

Why don't you check google. It tells you all the sorting algos and what their time complexity is.

[Rayhan Muktader]

Since the arrays are sorted, you can use a binary search for this problem. That would make the what method n(log n). Take the middle value of the array and compare it to the value you are searching for. You found your answer if the values match. Or the value you are searching for would be in the first half of the array if the middle value is greater than the value you are searching for. Or the value you are searching for is in the second half of the array if the middle value is less than the value you are searching for. Now take the half of the array where value is located and repeat the same procedure. You are splitting the array in half every time you do this. Which makes binary search a log n operation. Since you are searching for n values from array 1, your what method will be n(log n).

Here is link to an example: http://www.geocities.com/cool_ranju/bsearch.html

It will make sense if you trace the code on paper.