Both DFS and BFS achieve O(V+E) time complexity, and that bound is information-theoretically optimal: any algorithm that touches every reachable vertex and every edge exactly once cannot do better, because reading the input is itself an O(V+E) operation. Linear complexity emerges from the constraint that each edge can be traversed at most twice (once from each endpoint), and the addition rather than multiplication of V and E reflects the sparse-vs-dense distinction baked into the model.
The bound is a hard floor, not a current best. No algorithm can solve graph connectivity in less than O(V+E) time, regardless of cleverness, because the answer depends on every vertex and every edge in the worst case. This is the difference between a complexity that engineering can attack (sub-quadratic sorting, sub-linear approximate counting) and one that information theory rules out.
Graph representation choices (adjacency list versus matrix) move constants and cache behavior, not the asymptotic class. They matter most for very sparse graphs (where matrix wastes space on zero entries) or very dense graphs (where list traversal pays for pointer-chasing). Real-world performance on huge graphs often turns on those constants, but the algorithmic ceiling is fixed. The lesson generalizes: knowing where the lower bound sits prevents wasting effort on optimizations that physics ruled out, and pushes the question to “is there a better problem formulation?” instead of “is there a better algorithm?“. See Search Strategies Trade Information Gain Against Entropy for the per-step analysis underneath this aggregate bound.