Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [time-complexity]

For questions related to the time complexity (e.g. in Big-O notation) of AI and ML algorithms.

Filter by
Sorted by
Tagged with
0 votes
1 answer
28 views

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 ...
Deyan's user avatar
  • 1
0 votes
1 answer
70 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 ...
GABRIEL ÁNGEL CANALS SALLERAS's user avatar
0 votes
1 answer
366 views

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 ...
ImposterX1's user avatar
0 votes
1 answer
52 views

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 ...
white's user avatar
  • 1
0 votes
0 answers
46 views

Are autoencoders computationally cheaper than MLPs with the same number of neurons?

Are autoencoders computationally cheaper than other neural networks such as MLP with the same number of neurons? I have read in some papers that autoencoders train the network faster, and I could ...
Jesus M.'s user avatar
1 vote
2 answers
2k views

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: ...
user26866's user avatar
  • 111
0 votes
1 answer
166 views

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(...
wd violet's user avatar
  • 103
1 vote
1 answer
3k views

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. ...
Anik Islam Abhi's user avatar
0 votes
0 answers
289 views

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. ...
farnad's user avatar
  • 1
2 votes
2 answers
554 views

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{...
user153245's user avatar
2 votes
0 answers
183 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 ...
FoundABetterName's user avatar
3 votes
1 answer
382 views

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 ...
Ron Germano's user avatar
3 votes
0 answers
430 views

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 ...
rahul tomar's user avatar
0 votes
0 answers
408 views

What is the time complexity for training a single-hidden layer auto-encoder?

What is the time complexity for training a single-hidden layer auto-encoder, for 1 epoch? You can assume that there are $n$ training examples, $m$ features, and $k$ neurons in the hidden layer, and ...
Mohsen Fazaeli's user avatar
1 vote
1 answer
146 views

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 *...
Karthik's user avatar
  • 11
1 vote
1 answer
609 views

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....
Ruli's user avatar
  • 153
0 votes
1 answer
10k 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 ...
mftgk's user avatar
  • 9
2 votes
1 answer
573 views

Continuous state and continuous action Markov decision process time complexity estimate: backward induction VS policy gradient method (RL)

Model Description: Model based (assume known of the entire model) Markov decision process. Time($t$): Finite horizon discrete time with discounting factor State($x_t$): Continuous multi-dimensional ...
leodongxu's user avatar
1 vote
0 answers
61 views

Is subsection generation $O(n^4)$

When I say template matching, I'm referring to finding occurrences of a small image (the template) in a larger image. The OpenCV library provides the trivial solution, that slides the template over ...
Tobi Akinyemi's user avatar
2 votes
0 answers
1k views

What is the time complexity of the forward pass and back-propagation of the sequence-to-sequence model with and without attention?

I keep looking through the literature, but can't seem to find any information regarding the time complexity of the forward pass and back-propagation of the sequence-to-sequence RNN encoder-decoder ...
user1234544's user avatar
3 votes
2 answers
5k 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 ...
iRestMyCaseYourHonor's user avatar
4 votes
0 answers
73 views

Given an input $x \in R^{1\times d}$ and a network with $s$ hidden layers, is the time complexity of the forward pass $O(d^{2}s)$? [duplicate]

I have a neural network that takes as an input a vector of $x \in R^{1\times d}$ with $s$ hidden layers and each layer has $d$ neurons (including the output layer). If I understand correctly the ...
Jonathan Azpur's user avatar
2 votes
0 answers
87 views

What is the complexity of policy gradient algorithms compared to discrete action space algorithms?

I am using a policy gradient algorithm (actor-critic) for wireless networks. The policy gradient-based algorithm helps because it considers continuous action space. But how much does a policy ...
pratap's user avatar
  • 21
2 votes
1 answer
318 views

Prove that in such cases, it is possible to find an ERM hypothesis for $H_n$ in the unrealizable case in time $O(mnm^{O(n)})$

Let $H_1$ , $H_2$ ,... be a sequence of hypothesis classes for binary classification. Assume that there is a learning algorithm that implements the ERM rule in the realizable case such that the ...
Ben's user avatar
  • 253
11 votes
1 answer
7k views

What is the time complexity of the forward pass algorithm of a feedforward neural network?

How do I determine the time complexity of the forward pass algorithm of a feedforward neural network? How many multiplications are done to generate the output?
Artificial's user avatar
2 votes
0 answers
236 views

What is the time complexity of an unparellelized Monte Carlo tree search?

I am writing a report where I used a slightly modified version of MCTS (not parallelized). I thought It could be interesting if I could calculate its time complexity. I'd appreciate any help I could ...
ATidedHumour's user avatar
4 votes
1 answer
73 views

Can machine learning be used to improve the average case complexity of an algorithm?

I am developing an algorithm that, in certain moment, must explore an exponential number of objects derived from a graph: ...
Guillermo Mosse's user avatar
2 votes
1 answer
198 views

Which algorithms, between ant colony or classical routing algorithms, have a better time complexity for the shortest path problem?

Which algorithms, between ant colony or classical routing algorithms, have a better time complexity for the shortest path problem? In general, can we compare efficiency of these two types of ...
Questioner's user avatar
3 votes
1 answer
8k views

What is the time complexity of the value iteration algorithm?

Recently, I have come across the information (lecture 8 and 9 about MDPs of this UC Berkeley AI course) that the time complexity for each iteration of the value iteration algorithm is $\mathcal{O}(|S|^...
Shifat E Arman's user avatar
2 votes
1 answer
1k views

Why is exact inference in a Bayesian network both NP-hard and P-hard?

I should show that exact inference in a Bayesian network (BN) is NP-hard and P-hard by using a 3-SAT problem. So, I did formulate a 3-SAT problem by defining 3-CNF: $$(x_1 \lor x_2) \land (\neg x_3 \...
xava's user avatar
  • 423
2 votes
1 answer
257 views

What are some resources regarding the complexity of training neural networks?

In the paper "Provable bounds for learning some deep representations", an autoencoder like a model is constructed with discrete weights and several results are proven using some random-graph theory, ...
thecomplexitytheorist's user avatar
42 votes
4 answers
58k views

What is the time complexity for training a neural network using back-propagation?

Suppose that a NN contains $n$ hidden layers, $m$ training examples, $x$ features, and $n_i$ nodes in each layer. What is the time complexity to train this NN using back-propagation? I have a basic ...
user avatar
3 votes
0 answers
215 views

How can I calculate the number of matrix additions, multiplications and divisions in AlexNet?

I'm a first-year student in machine learning and I really recently started to immerse myself. I need to calculate number of: matrix additions matrix multiplications matrix divisions which are ...
Ivan Talalaev's user avatar
7 votes
2 answers
1k views

Can neural networks efficiently solve the traveling salesmen problem?

Can neural networks efficiently solve the traveling salesmen problem? Are there any research papers that show that neural networks can solve the TSP efficiently? The TSP is an NP-hard problem, so I ...
Gottfried William's user avatar