Questions tagged [space-complexity]
For questions related to the space complexity analysis of artificial intelligence algorithms.
11 questions
1
vote
1
answer
312
views
Why the space complexity of depth-first search is O(bm)?
In "Artificial Intelligence: A Modern Approach", the authors say that the space complexity of depth-first search is proportional to O(bm), considering b as the branching factor and m the ...
- 111
0
votes
1
answer
75
views
Unable to understand Figure 3.13 Artificial Intelligence: a Modern Approach
I'm currently studying the functionality of BFS and the AIMA book shows
.
I am unable to replicate them using some trivial calculations.
For example, if the BFS generates $10^6$ nodes per second and I ...
1
vote
1
answer
614
views
Instead of accumulating the gradient, can we accumulate loss values?
I have read and used Gradient Accumulation as a method to handle large batch size on smaller memory restrictions. It is described as following:
...
- 11
2
votes
0
answers
193
views
How would we get a good estimation of the asymptotic performance of machine learning algorithms?
The following question is from the webbook Neural Networks and Deep Learning by Michael Nielson:
How do our machine learning algorithms perform in the limit of very large data sets? For any given ...
2
votes
1
answer
3k
views
What is the space complexity for training a neural network using back-propagation?
Suppose that a simple feedforward neural network (FFNN) contains $n$ hidden layers, $m$ training examples, $x$ features, and $n_l$ nodes in each layer. What is the space complexity to train this FFNN ...
- 121
1
vote
1
answer
2k
views
What is the space complexity of bidirectional search?
Is the space complexity of the bidirectional search, where the breadth-first search is used for both the forward and backward search, $O(b^{d/2})$, where $b$ is the branching factor and $d$ the length ...
user42125
2
votes
1
answer
6k
views
What is the space complexity of breadth-first search?
When using the breadth-first search algorithm, is the space complexity $O(b^d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?
user42125
1
vote
1
answer
3k
views
What is the space complexity of iterative deepening search?
When using iterative deepening, is the space complexity, $O(d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?
user42125
1
vote
1
answer
11k
views
What is the computational complexity of the forward pass of a convolutional neural network?
How do I determine the computational complexity (big-O notation) of the forward pass of a convolutional neural network?
Let's assume for simplicity that we use zero-padding such that the input size ...
- 19
2
votes
0
answers
191
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-...
- 481
3
votes
2
answers
6k
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 ...
