Time Complexity Analysis When Merging Routes

Question

I would like to know the best way to approach the time complexity analysis of the following algorithm. I have come up with 2 approaches so far.

We have a std::map<int,vector<int>> (Balanced Binary Search Tree). Each of the std::vector<int> will be called a route.

Algorithm:

1. while(true)
2. We pick the first two routes from the map and add their key values and if ((sum of key values)>capacity) 
   then break else proceed to step 3.
3. Now we have two routes which we merge. 
   After merging (we simply append one of the routes to the other), we delete the chosen two routes and 
   insert the new route into the map. 
   The key value of the new route will be the sum of the key values of the chosen two routes.
   Go to step 2.

Time Complexity Analysis:

• Approach 1

Let us consider the total number of routes to be n. Operations like insertion and deletion in the map will cost us O(log(n)) and extraction of the first element of the map will be O(1). When it comes to merging two routes, let us consider the average length of a route (vector<int>) to be N and so merging will cost us O(N). In the worst case, there will be (n-1)mergings and so overall time complexity in the worst case will be O(nN).

• Approach 2

Let us consider the total number of routes to be n and let us also consider k to be the total sum of lengths (vector.size()) of all the routes (vector<int>). Now time complexity of operations involving map remains the same. When it comes to merging, in the worst there can be (n-1) mergings and in total, we have k elements in all of the routes, so overall time complexity in the worst case will be O(nk).

Any help will be really appreciated.

Answer 1

I'll keep your terminology of $n$ being the number of routes, $N$ being the average length of a vector, and $k$ being the sum of the lengths of all vectors. Then $N = k/n$. Your first approach it's implying that the cost of merging can be assumed to be $O(N)$, but this is only true at the beginning; when you're approaching the end of the process, the average length will be much closer to $k$. I propose a way to analyze this getting to a reasonable bound.

First, let me suggest the following: when merging two lists $A$ and $B$, always concatenate the smaller one at the end of the larger one.

In order to understand the cost of the algorithm, let's decompose it into two parts, the ones associated with the map data structure, and the ones associated with the merging.

• If the main loop makes $i$ iterations, you'd be paying $O(i \lg n)$ in operations related to the map. As each iteration is reducing the number of routes by $1$, you can have at most $n$ iterations, and thus the total cost for interacting with the map is at most $O(n \lg n)$.

• On the other hand, for the merging cost, let us charge an element whenever it is merged into another list. For example, when merging $[3,2,4,5]$ with $[2,9,7]$ we would be charging one operation to $2$, one operation to $9$, and one operation to $7$. More in general, when merging $A$ and $B$ with $|A| > |B|$, we charge every element of $B$ one operation. Note that as $|A| > |B|$ then the resulting list is at least double the size of $B$; namely $|A \cup B| > 2|B|$. As the final list has $k$ elements, and each time an element is charged its corresponding list doubles its size, we know that each element can be charged at most $\lg k$ times. But also we know that no element can be charged more than $n-1$ times. So the total number of times an element can be charged is $\min(n-1, \lg k)$ and thus the total cost is $O(k \min(n, \lg k))$.

We thus have that the total cost is $O(n \lg n + k \min(n, \lg k))$, and as $k > n$, we can simply say $O(k \min(n, \lg k))$. Note that if $n < \lg k$, then this approach results in $O(kn)$ as your second approach.