Questions tagged [time-complexity]
For questions related to the time complexity (e.g. in Big-O notation) of AI and ML algorithms.
33 questions
1vote
2answers
187views
How to Determine the Time Complexity of Machine Learning Models for Prediction?
I am used to calculating the time complexity of algorithms and data structures to understand how my code will perform in a production environment. However, when using machine learning (ML) and AI-...
- 123
0votes
1answer
47views
How to estimate Time vs Memory trade-off prior to modelling
It is often the case when the time vs memory trade-off is underestimated prior to using ML/DL for solving a particular task. Taking into account the type, size and format of the available data and ...
0votes
1answer
86views
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 ...
0votes
1answer
991views
What does the branching factor mean in the time complexity of Breadth-First Search (BFS)
Can someone explain where my math is off here? I am confused on the b - Branching Factor and how to calculate the worst-case scenario when running BFS. In a worst-case scenario BFS would have to hit ...
0votes
1answer
75views
The complexity order of regret (especially in online reinforcement learning)?
In online reinforcement learning theory, how to judge the complexity order of regret, if there are two or more terms in there? For example, the state space is $X$, the action space is $A$, the episode ...
1vote
3answers
3kviews
Why should one expect the backward pass to take twice as long as the forward pass?
I have seen it stated that, as a rule of thumb, a backward pass in a neural network should take about twice as long as the forward pass. Examples: From DeepSpeed's Flops Profiler docs, the profiler: ...
- 111
0votes
1answer
196views
Why is the time complexity of the Triplet Loss $O(N^3)$
The triplet loss function uses an anchor, positive, and negative examples. If $N$ are the number of examples in the training set with $C$ classes, then I think that the time complexity should be $O(...
- 103
1vote
1answer
4kviews
What is the time complexity for testing a stacked LSTM model?
In the data preparation phase, we have to divide the dataset into two parts: the training dataset and the test dataset. I have seen this post regarding the time complexity for training a model. ...
0votes
0answers
358views
What is the time complexity of DDPG algorithm?
Suppose we have a DDPG algorithm. The actor has N input nodes, two hidden layers with J nodes, and S output nodes. The critic has N+S input nodes, two hidden layers with C nodes, and one output node. ...
2votes
2answers
813views
Why is there a 1 in complexity formula of uniform-cost search?
I am reading the book titled Artificial Intelligence: A Modern Approach 4th ed by Stuart Russell and Peter Norvig. According to the book, the complexity of uniform-cost search is as $$ O(b^{1+\lfloor{...
- 185
2votes
0answers
209views
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 ...
3votes
1answer
570views
What is the most computationally efficient genetic algorithm?
In researching genetic algorithms, it seems that there are various methods of selection and other operator methods that can significantly change the performance. For example, this picture contains ...
3votes
0answers
505views
What is the time complexity for training a gated recurrent unit (GRU) neural network using back-propagation through time?
Let us assume we have a GRU network containing $H$ layers to process a training dataset with $K$ tuples, $I$ features, and $H_i$ nodes in each layer. I have a pretty basic idea how the complexity of ...
1vote
1answer
161views
Why does CNN forward pass take longer compared to MLP forward pass? [closed]
Let's take a 32 x 32 x 3 NumPy array and convolve with 10 filters of size 2 x 2 x 3 with stride 2 to produce feature maps of volume 16 x 16 x 10. The total number of operations - 16 * 16 * 10 * 2 * 2 *...
- 11
1vote
1answer
752views
What is the time complexity of the upsampling stage of the U-net?
I am trying to determine the complexity of the neural network we use. The neural network is a U-net generator with an input shape of NxN (not an image but image-like data) and output of the same shape....
- 153
