-1
$\begingroup$

This question already has an answer here:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays.

Example 1:

nums1 = [1, 3] nums2 = [2]

The median is 2.0

Example 2: nums1 = [1, 2] nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Here is my solution:

//Find out the median of two sorted array
public class Median {
public static void main(String args[]){
    int arr1[]={1,2,6};
    int arr2[]={3,5,7};

    int temp[]=new int[(arr1.length)+(arr2.length)];
    int k=0,i=0,j=0,mid=0,k2=0;


    while(i< arr1.length && j<arr2.length) {
        if (arr1[i] < arr2[j]) {
            temp[k] = arr1[i];
            i++;
        } else {
            temp[k] = arr2[j];
            j++;
        }
        k++;
    }
    while (i < arr1.length) {
        temp[k++] = arr1[i++];
    }
    while (j < arr2.length) {
        temp[k++] = arr2[j++];
    }

    int a= temp.length;
    if(a%2==0){
        k2=(temp.length)/2;
        mid = (temp[k2]+temp[k2-1])/2;
    }
    else{
       int k1=(int)(temp.length)/2;
        mid=temp[k1];
    }
    System.out.println("The median of two sorted array is "+mid);
}
}

I want to know that what is the time complexity of my code? Is there any better way to solve this?

I know how to find out the time complexity if there is for loop. But if there is while loop then how could I find out the time complexity?

$\endgroup$

marked as duplicate by Raphael Nov 19 '18 at 11:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Nov 19 '18 at 11:08
  • $\begingroup$ Note that debugging/reviewing code is offtopic here, and performing analysis for you is not a type of request we want to entertain. $\endgroup$ – Raphael Nov 19 '18 at 11:09
  • $\begingroup$ There's no significant difference between while loops and for loops. If you understand how to do one (as distinct from just having some recipe that you use because you've been told that it works), you understand how to do the other. $\endgroup$ – David Richerby Nov 20 '18 at 12:06
  • $\begingroup$ @Raphael Can you please share the link where this question ask previously? I am very curious to know that. $\endgroup$ – Encipher Nov 20 '18 at 19:05
  • $\begingroup$ The linked reference question tells you how to analyze loops in general. You can also check out algorithm-analysis+loops. $\endgroup$ – Raphael Nov 20 '18 at 20:04
0
$\begingroup$

Let’s say two arrays have a million elements each. A [500,000] = 3,516 and B [500,000] = 12,920. Can you say anything about the median? Is there anything you can do with this information to save a lot of work? What if A[750,000] = 11,416?

Your code takes O(n+m) both in time and space. This can be done in O(ln n + ln m).

$\endgroup$
  • $\begingroup$ Why not? If I have million of input the code works as it works previously. Why are you asking that? Is there any flaw in the code? Secondly how could you find out the time complexity. Is it not depend upon while loop? $\endgroup$ – Encipher Nov 19 '18 at 20:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.