24.1.5. Algorithm Complexity

So, let us apply the strategy to this DAG, so we first begin by labelling every vertex by its in degree. So, will read we have indicated the in degree of every vertex. So, for instance, 1 and 2 have no incoming edges. So, they have in degree 0, vertex 3 has 2 edges coming, as in degree 2, vertex 8 has 4 edges coming inside and in degree as 4 and so on.

The algorithm begins by analyzing a Directed Acyclic Graph (DAG) to determine the 'in-degree' of each vertex. The in-degree is simply the number of edges coming into that vertex. For example, vertices 1 and 2, having no incoming edges, have an in-degree of 0. Vertex 3, with two incoming edges, has an in-degree of 2, and vertex 8, with four incoming edges, has an in-degree of 4. This labeling is crucial as it establishes which vertices can be processed next.

Think of it like a team project where each task has dependencies from other tasks. For example, if Task 1 and Task 2 need no other tasks to start (like 1 and 2), they can be started immediately. However, Task 3 can only begin once two previous tasks are complete (like vertex 3). Knowing who is ready to work helps in planning the project efficiently.

Now we have to pick a vertex of in degree 0 enumerated and eliminated. So, we have a choice between 1 and 2, so let us suppose we start with 1, we eliminated and now when we eliminated we also eliminate the edges going out of it.

Once the in-degrees are calculated, the next step is to start processing the vertices with an in-degree of 0 (no dependencies). We can choose either vertex 1 or 2, and for this explanation, we opt for vertex 1. When we 'eliminate' it, not only are we marking vertex 1 as processed, but we also decrement the in-degrees of the vertices it points to (3, 4, and 5). This reflects that one prerequisite has been completed for each of those tasks.

Imagine you're in a board game where you can only play certain moves if you've completed the previous ones. Once you complete a move (like eliminating vertex 1), you clear the way for subsequent moves. If you completed Task 1, it now allows Task 4 and Task 5 to begin.

So, what happens on elimination of 1 is that we enumerated and we reduce the in degrees of 3, 4 and 5 from 2, 1, 1 to 1, 0, 0.

As we eliminate vertex 1, we reduce the in-degrees of the vertices it was connected to. Initially, the in-degrees of vertices 3, 4, and 5 were 2, 1, and 1, respectively. After removing vertex 1, their in-degrees are updated to 1, 0, and 0. This indicates that these vertices are now either available or ready to be processed, as vertex 4 is now at an in-degree of 0, meaning it can now be enumerated as well.

Think of it as a restaurant where each server has to wait for someone to finish their task before they can serve their next dish. When one server (vertex 1) finishes their dish, they allow two others (vert 4 and 5) to become available, as they no longer have someone blocking their task.

Now we have three choices, two the original one which are in degree 0 and we have two new vertices 4 and 5 which correspond to tasks if you want to call them, whose prerequisite has been completed.

After processing vertex 1, we are left with several options for what to process next. Besides the initial vertex with in-degree 0 (vertex 2), vertices 4 and 5 are now also eligible, as all their prerequisites (in this case, vertex 1) have been completed. This flexibility of choice is important in optimizing the order of processing vertices in the algorithm.

In a video game, after completing a quest, several new quests may become available. You can either choose a quest that was already available or opt for a new one that just became open due to your earlier completion.

So, what is the complexity of the algorithm? It is fairly easy to see that for this adjacency matrix representation, it is n squared, as we saw initializing the in-degree itself takes time n squared.

The complexity of this algorithm in its current form, utilizing an adjacency matrix, is O(n²) due to the nested looping required to initialize and update the in-degrees. The algorithm has an outer loop through n vertices, and for each vertex, there's an inner loop also iterating through n edges, leading to the quadratic complexity.

Picture a classroom where every student (n) must pair up with every other student for a group activity. If you have 30 students, the number of interactions becomes 30 x 30 = 900 interactions. That's analogous to our n² complexity.

By using an adjacency list, we can bring down this time to linear from n squared we can bring it down to order n plus m.

Switching from an adjacency matrix to an adjacency list allows the algorithm's complexity to improve significantly, from O(n²) to O(n + m), where m is the number of edges. This is because the algorithm can directly access neighbors for each vertex without needing to scan through all possible edges, significantly speeding up processing time.

Imagine using a telephone directory versus a smartphone's contacts app. The contact list on a smartphone lets you find numbers (edges) directly through the app, making it faster to look up. In contrast, a paper directory necessitates searching through all the names, resembling the adjacency matrix approach.

--