Stuck with couple of possible scenarios, can anyone help?


#1

Questions:

Are two arrays of same length or different lengths?

and, same old question, Why can’t it be O(n*n)

This is what I observed

lets say arr[i] = [2,3,4,5,6,7,8,9,10]; arr[j] = [3,4,5,6,7]

for i = 0; the inner loop iterates ‘n’ times because ( j < n && arr[i] < arr[j] ) succeeds for all j & i = 0; here time complexity is O(n) and the loop breaks when j equals to n

Now, the outer loop still runs for ‘n’ times

so why can’t it be O(n*n)

The arrays I considered aren’t the worst case scenario?

Can someome help me in understanding this please ?


#2

Let’s get to the problem, we are interested in finding the worst case of this problem that is Big O. Consider the worst case that outer loop will run total ‘n’ times and inner loop will also run ‘n’ times and assume the array is in ascending order, so arr[i]<arr[j] is always true. So our main concern now is “j<n” condition in while loop.
Normally we would say that the complexity of this problem is O(n^2) because they are nested loop, but here is the thing in this problem.
If you see closely that j is global initialized with 0 and it is never initialized with ‘i’ inside any of the loops. So for our very first iteration when ‘i=0’ our while loop will run ‘n’ times since we assumed array to be ascending order. For other values of i such that ‘i=1,2,3…n’ while loop will be always false because ‘j’ does not satisfy the condition it is already equal to ‘n’.
So our i loop will run ‘n’ times and so our complexity becomes O(2*n), therefore O(n).
I hope you understood !


#3

I understood why you said our loop run 'ni times. But after that how did you say that Complexity is O(2*n) .Isn;t it directly O(n)?


#4

i=0, j=0;
arr[0]<arr[0] this condition never gets true therefore while loop runs for one time only for each value of i
therefore program runs N times
hence O(N)


#5

Should they also mention what kind of an array it is? Ascending, descending, random. Please explain me the case when the array is random.


#6

On what basis we are assuming arr to be in ascending order?


#7

Here O(2*N) is same as O(N+N) which comes to O(N)


#8

No the order must not be mentioned as we always need to look for the worst case. Here the worst case is when the condition stands true anyhow at its maxm possible. here if we dry run on descending array then only we find that arr[i] < arr[j] till its end. hence we choose descending order