1

So, basically I wanted to find all the elements in the second array which are less than or equal to the element of 1st array. Both the arrays are sorted. I know the solution. I don't want that. I just want to know the time complexity of this program and how will we calculate it. Thank you in advance.

int count=0;
        for(int i=0;i<n;i++)
            {
            for(int j=count;j<m;j++)
                {
                if(arr[i]>=arr[j])
                    //some O(1) code
                else
                    {
                    count=j;
                    break;
                    }
                }
            }
Manas Tyagi
  • 11
  • 2
  • now the code is completely broken ;) It won't run anymore – kai Feb 17 '19 at 10:14
  • Sorry man. Didn't even if it was running or not. Have a look at this. – Manas Tyagi Feb 17 '19 at 10:53
  • now, as it stops at i=j , count will be set to i/rsp.ex (i+1). so the inner loop does one comparison. O(n). it in essence does if(arr[i]>=arr[i]) - yes same index i - that is the element is compared with itself for every element (duplicates run one step further in the inner but will then be skipped in the next iteration: no difference). you can achieve that with a single loop – kai Feb 17 '19 at 17:07

4 Answers4

3

The complexity will be O(n*m) simply because the outer loop for each value of n will run m times.

Ted Lyngmo
  • 93,841
  • 5
  • 60
  • 108
abdulwasey20
  • 747
  • 8
  • 21
2

Well there is only one array in your code. In contrary to your explaination that says there are two arrays.

Assuming there is a typo and there should be a second array:

Worst: You can establish an upper bound at O(n * m). Happens if all elements in the second are smaler than in the first.

Best: You can establish a lower bound at O(n) . Happens if all elements of the second are bigger than in the first(first element breaks the loop).

Average: If you asume an even distribution you get an average at O(n * m / 2).

Conclusion Its a O(n²) league algorithm.

Only one array:

However if I take the code "as is" - only one array and also take into account that it is sorted:

If arr1[i] < arr2[j] for i < j holds: It will skip the inner loop for j>i. -> the inner loop will stop at j==i; -> upper bound at O(n * m / 2). Still an O(n²) league.

Reverse Order

So arr[i] < arr[j] for i>j holds:

It will skip the inner loop for j < i so the inner loop will be executed at most one time: O(n+m) rsp. O(n).

But I guess it is a typo and you ment two arrays so I skip the case sorted with duplicates(it is again O(n*m) eg. if all elements are the same).

kai
  • 894
  • 1
  • 7
  • 15
  • Thanks for the valuable explanation. But I made a mistake while posting the question. Have a look at the edits now and please help me. :) – Manas Tyagi Feb 17 '19 at 10:09
1

O(n*m)- since you are going through 'n' outer elements and for each outer element you have an inner loop with m elements. For loops time complexity - O(n). Basically how many times the for loop will run.

Ravi
  • 39
  • 6
0

Complexity : O(m*n)
As two for loops involved in this, it may be vary in different cases but it has to be O(m*n) if both gets executed.

iamrajshah
  • 963
  • 1
  • 11
  • 23