# What is the algorithmic complexity of DFS under the cache oblivious model?

Consider the basic non-recursive DFS algorithm on a graph G=(V,E) (python-like pseudocode below) that uses array-based adjacency lists, a couple of arrays of size V, and a dynamic array stack of size <= V. If I understand correctly, this is a cache oblivious algorithm since no information about the memory configuration is provided. Moreover, even if we suppose that every memory access in this algorithm produces a cache miss (the number of cache misses per line is given in comments), we would still have O(V+E) memory transfers, so I postulate this would be a worst case complexity upper bound under the CO-model. Is this correct?

def dfs(G, s):
visited = [False for v in G] # V
stack = [s] # 1
nxt = [0 for v in G] # V
degree = [len(v) for v in G] # V + E
while stack:
v = stack.pop(-1) # 1
visited[v] = True # 1
while nxt[v] < degree[v] and visited[G[v][nxt[v]]]: # 6
nxt[v]+=1 # 1
if nxt[v] < lens[v]: # 2
stack.append(v) # 1
stack.append(G[v][nxt[v]]) # 3

def main():
#  e.g. dfs order of this graph is 0 1 2 3
#
#  0 -> 2
#  | \  ^
#  |  \ |
#  v   v
#  3 -> 1
#
G = [[1,3,2],,[],]
dfs(G,  0)

• If an algorithm executes $O(f(n))$ statements each of which costs $O(1)$ (time, memory access, ... any additive cost measure works here), then the whole algorithm costs $O(f(n))$. That much is obvious just from the definition of Landau-$O$. So what't the question, really? – Raphael Nov 2 '16 at 7:57
• Yes, "Big-Oh" is not suitable for analyses of this kind. You'll have to look more closely. – Raphael Nov 2 '16 at 7:58
• @Rapahel Thanks. Actually, Arge et al  proposed cache oblivious graph traversal algorithms (DFS/BFS) based of buffered repository trees that match the I/O model bound of O((V+E/B)*lg V + sort(E)) memory transfers (B=block size). What I fail to understand is how this is better than the straightforward O(v+E) bound.  Arge et al. An optimal cache-oblivious priority queue and its applications to graph algorithms. SIAM J. Comput, 2005. – Paulo Nov 2 '16 at 13:41
• I don't, either. I don't even understand what that O-term is supposed to mean. Is B constant? If not, what's it's limiting process? Imho, there's too much abuse of notation and no useful statement at all. – Raphael Nov 3 '16 at 23:15
• In the external memory I/O model, B is the "block size" (like in B-trees). In the cache-oblivious model, this is equivalent to the length of a cache line, a fixed parameter (the other is M, the # of cache lines) that is however unknown to the algorithm. The general goal is to devise algorithms that perform just as well w.r.t #memory accesses, without issuing explicit I/O operations (being thus oblivious to the memory), but rather accessing data directly from the cache and relying on an "ideal" cache replacement mechanism. – Paulo Nov 4 '16 at 12:13