Time complexity of building a heap relative to two arguments, N and M

user_16558909 0
Viewed 57

Using the below code as an example:

public void method bigO(int N, int M){
    PriorityQueue<Integer>> minHeap = new PriorityQueue<Integer>();

    for (int i = 0; i < M; i++) {
         minHeap.add(i);
    }

    for (int i = 0; i < N; i++) {
         minHeap.add(i);
    }
}

The first loop would have time complexity of O(M log(L)) where L is the size/length of the heap. Similarly, the second loop would have complexity O(N log(L)). Since both M and N are linear terms, how would you determine the overall complexity? Would the overall complexity be something like Max(M log(L), N log(L))?

big-o time-complexity java
2 Answers

You could think of it like this: since your code is performing both loops sequentially in their entirety, you are doing M add calls and then another N add calls. That is a total of M + N add calls.

Each add call has a time complexity of O(log(L)). But since you are adding M things in the first loop and N things in the second loop your L is growing linearly as M + N does.

Putting that together you get (M + N) * log(M + N) or L * log(L), where L is the amount of total items you have to deal with.

So your code has O(n * log n) time complexity - linearithmic.

user_24222240

minHeap.add is log(n) where n is the size of the heap. Therefore, building a heap from an array of n elements is O(n log(n)).

Now, you're doing this operation twice for two unrelated variables, n and m, so you'd normally add them together, O(n log(n) + m log(m)).

However, as pointed out in the comments, this is slightly inaccurate because the second operation adds to the existing heap of size n, giving O(n log(n) + m log(m + n)).

There's not enough information to be able to drop one of the variables since either one might dominate; this is captured in your Max() call, but I would avoid it because it's already implied by the O notation. I'd avoid the variable L as well--we're starting from an empty queue, so we can use n and m precisely.

user_62433520
Related