Questions tagged [space-complexity]

For questions related to the space complexity analysis of artificial intelligence algorithms.

Filter by
Sorted by
Tagged with
2
votes
0answers
65 views

What is the memory complexity of the memory-efficient attention in Reformer?

When I read the paper, Reformer: The Efficient Transformer, I cannot get the same complexity of the memory-efficient method in Table 1 (p. 5), which summarizes time/memory complexity of scaled dot-...
2
votes
1answer
152 views

Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$?

I am reading through Artificial Intelligence: Modern Approach and it states that the space complexity of the GBFS (tree version) is $\mathcal{O}(b^m)$. While I am reading, at some points, I found ...