# Finding time complexity when while loop included [duplicate]

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?

• 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?
– Raphael
Nov 19, 2018 at 11:08
• Note that debugging/reviewing code is offtopic here, and performing analysis for you is not a type of request we want to entertain.
– Raphael
Nov 19, 2018 at 11:09
• 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. Nov 20, 2018 at 12:06
• @Raphael Can you please share the link where this question ask previously? I am very curious to know that. Nov 20, 2018 at 19:05
• The linked reference question tells you how to analyze loops in general. You can also check out algorithm-analysis+loops.
– Raphael
Nov 20, 2018 at 20:04

## 1 Answer

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).

• 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? Nov 19, 2018 at 20:32