CODEWITHSUNDEEP
algorithm
Yiping
Yiping

Reputation: 1061

Time complexity with inner iterator inside a loop

I want to check whether there is duplicated element in two sorted array with similar size by using simple linear search, not binary search.

So I will scan the element of first array, and I keep moving the iterator on the second array next (since it is sorted). In each loop, the iterator may move 1 or more steps, but the totally steps is bounded by the size of second array.

May I say it is O(n) or O(n^2)?

Upvotes: 1

Views: 236

Answers (3)

displayName
displayName

Reputation: 14379

Description

For every element in the outer array, you are going to the inner array and moving ahead to check if this element is present in the inner loop or not. Note that you are not iterating all the elements of inner loop for every outer loop element. Whereas, O(n^2) is the case where for every element in outer loop, you iterate through every element in the inner loop (or at least some O(n) elements of the inner loop).

Since the arrays are sorted, essentially you will iterate the inner loop elements one time only. Ex, if outer array has {1, 3, 7} and inner one has {2, 4, 5}, your inner and outer loop's iteration will look like

  • For outerPointer = 1, innerPointer stays at 2 as 2 > 1
  • For outerPointer = 3, innerPointer touches 2, then touches 4 and stays there 4 > 3
  • For outerPointer = 7, innerPointer touches 4, then touches 5 and then we break come out of both loops.

We will go, at max, to O(n) for outer loop. We can break early too if inner loop is finished before outer loop as it has happened in the above example. For sure we will iterate through all elements in the inner loop, but at max it will be O(2n) = O(n) only. I said O(2n) as there is the the case when you touch every element of inner array twice.

Thus, for all elements in outer loop, you will move the inner loop for a total of O(n) only. Total maximum touches are therefore equal to 3n (n for outer and a max of 2n for inner), or we can say that the run-time is O(3n) which is equal to O(n).

Mathematical Proof

  • Let both arrays have n elements

The pseudocode for the testing if a duplicate element exist would be:

01. set o = 0, i = 0, lastInnerArrayIndex = 0

02. for outerArrayIndex going from 0 to n - 1

03.     if lastInnerArrayIndex == n, break;
04.     o = outerArray[outerArrayIndex]

05.     for innerPointer going from lastInnerArrayIndex to n - 1
06.         lastInnerArrayIndex++;
07.         if o == innerArray[innerPointer]
08.             print ("common element found")
09.             exit;
10.         else if o < innerArray[innerPointer] break;

11.     end inner for

12. end outer for
  • Let's say for first element of outer array, we moved k1 elements, for second we moved k2 and so on till the nth element of outer loop for which we moved kn.
  • So one sample values for n = 10 can be:
    • k1 = 5 for elements 0 to 4
    • k2 = 2 for elements 5 and 6
    • k3 = 3 for elements 7 to 9
    • Therefore, Summation(k) = 5 + 2 + 3 = 10 = O(n)

Now,

  • total running time = k1 + k2 + k3 + k4 + ... + kn
  • total running time = n. Why? Because sum of all k's here is equal to total elements in the inner loop.

Case - 1: There is a common element in outer and inner array

In this case, at some km we will meet the if condition and all the k values from k(m+1) till kn will be 0, thus running time will be under O(n).

Case - 2: The last inner element is smaller than the last outer element

In this case, assuming that arrays are sorted in increasing order, the inner loop will again end at some km and thus running time will be of the order of inner loop element count which is O(n).

Case - 3: The last inner element is >= last outer element

The inner and outer loop will go till the last value, but that will effectively be taking n runs only as Summation(k) = O(n).

Hence, the running time of this iteration is O(n).

Upvotes: 2

Tagir Valeev
Tagir Valeev

Reputation: 100169

Suppose your first array has n size and second array has m size. At the worst case you need n+m iterator movements and n+m comparisons. Thus the complexity is O(n+m).

Upvotes: 1

JavierFromMadrid
JavierFromMadrid

Reputation: 621

If I have understood well the problem, the worst case would be that you search for an element which is at the end of both arrays. On that case you would have O(2n), being n the size of the biggest array. So yes, complexity woud be lineal, O(n).

Upvotes: 1

Related Questions