CODEWITHSUNDEEP
javaarraysalgorithmlinked-list
Cache
Cache

Reputation: 501

run time of two nested while loops inside a for loop

I am very confused while trying to find the complexity of an algorithm with a for loop and 2 nested while loops inside it that concern two linkedLists. Consider the following code: 

public int func(ClassName b){
// int[] myArray = new Node[n]; 
Node curA;
Node curB;
int sum = 0;
 for(int i =0; i<n ; i++){
    curA = this.myArray[i];
    while(curA != null){
        curB = b.myArray[i]
        while(curB != null){
            if(curA.data.equals(curB.data) sum++;
            curB = curB.next;
        }
        curA = curA.next;
    }

  }
  return sum;
}

Just imagine that there two objects this and b of the same class(say ClassName) which contains as field myArray. Lets say we call function func from this object and pass b object. Every node in this.myArray[i] list will be compared to every node in b.myArray[i] list. We do not know how long is the list in each element of myArray. Some times may the b.myArray[i] be equal to null or even this.myArray[i] be equal to null which will reduce the iterations and run time i think. I thought that this complexity would be O(n^3). But is this correct? I am sure about the for loop which has complexity O(n) but i am not sure what is going on with the while loops. Any help will be appreciated!

Upvotes: 1

Views: 329

Answers (2)

Anton
Anton

Reputation: 3203

It seems that the source of your confusion is trying to express the time complexity of the algorithm in terms of a function of n. It is not possible if lengths of the lists are independent of n.

For every i from 0 to n-1 let Ai be the length of the list this.myArray[i] and Bi be the length of the list b.myArray[i].

The exact number of times the innermost loop is executed is:

A0×B0 + A1×B1 + ... + An-1×Bn-1

In order to determine the time complexity you need to put some limits on the values of Ai and Bi.

A few examples:

  • Suppose the length of every list is bounded by M.

    Ai ≤ M for every i from 0 to n-1

    Bi ≤ M for every i from 0 to n-1

    A0×B0 + A1×B1 + ... + An-1×Bn-1 ≤ n×M²

    So the time complexity is 𝛰(n×M²).

  • Suppose the total number of elements in the lists of every object is bounded by K.

    A0 + A1 + ... + An-1 ≤ K

    B0 + B1 + ... + Bn-1 ≤ K

    A0×B0 + A1×B1 + ... + An-1×Bn-1 ≤ (A0 + A1 + ... + An-1)×(B0 + B1 + ... + Bn-1) ≤ K²

    So the time complexity is 𝛰(K²).

  • Suppose you don't know how long the lists can be. Then the upper bound on the execution time in not known either. The most you can tell is that the lower bound is Ω(n) because the outermost loop will always be executed n times.

Upvotes: 1

jrusev
jrusev

Reputation: 46

So to clarify, the myArray field is an array of linked lists. This is what your code actually does if expressed in pseudocode:

for each index i in this.myArray
  iterate over all elements of this.myArray[i]
    iterate over all elements of b.myArray[i]
      do O(1) work

If the length of this.myArray is N, the max length of the lists in this.myArray is M, and the max length of the lists in b.myArray is K, then the runtime complexity is O(M x N x K).

Upvotes: 0

Related Questions