Edmonds-Karp runs in time. Here is why: Each BFS takes time. The number of augmenting paths is at most , because each augmentation increases the distance from source to some node. Total: . For sparse graphs (), this is . For dense graphs (), this is .
In practice, the algorithm often runs much faster than the worst-case bound.
Space complexity is for the data structures used.