CODEWITHSUNDEEP
big-otime-complexity
MNRC
MNRC

Reputation: 263

What is the asymptotic worst-case running time of this function?

I'm trying to figure out the asymptotic worst-case running time for a function that calls another function:

The function being called (checks whether integer x is an element of linked list q):

boolean chkitem (int x, IntList q) {
  while (q != null) {                // q times
    if (x == q.value) return true;   // q times
    q = q.next;                      // q times
  }
  return false;                      // constant time
}

The function doing the calling (checks whether list p is a subset of list q):

boolean chklist (IntList p, Intlist q) {
  while (p != null) {                       // takes p time
    if (!chklitem(p.value, q)) return false; // takes p * 3q time?
    p = p.next;                             // takes p time
  }
  return true;
}

The first function seems to take a total of 3q time. But I can't figure out exactly how much time the second function takes. Is it 2p + p * 3q time? Dropping constants I got O (p+q).

Upvotes: 0

Views: 94

Answers (1)

ChronoTrigger
ChronoTrigger

Reputation: 8607

For each item in one list, you traverse the other list (completely in the worst case). So it is O(N*M), being N and M the length of the lists.

Upvotes: 1

Related Questions