Let's say I have an adjacency list, for example:
A1: b1 b2 b3
A2: b3 b4
A3: b4
A4: b1 b3 b4
What would be the time complexity to find the length of each 'sublist' in the whole adjacency list. The output being:
[A1: 3, A2: 2, A3: 1, A4: 3]
Since it is an adjacency list, I thought it would be O(E+V). But since we're kind of iterating through everything, is it actually O(E*V), like a nested for loop?
Been looking everywhere and I'm still struggling, thanks in advance for your help!
In the end, what you are doing is iterate through the edges. But if there are more vertices than edges, you still iterate through all the vertices. What you are not doing is iterate through all the edges in the graph FOR EVERY vertex.
O(E + V) is just another way of saying O(max(E, V)). So the algorithm is linear, it just means that if you have 1 edge but n vertices, it's still O(n) and not O(1).