Artificial Intelligence Stack Exchange
Artificial Intelligence Stack Exchange

Questions tagged [time-complexity]

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

Time complexity can, in some sense, be understood as time measured in computational operations.

For a more precise definition, see: Time Complexity (wiki)

Additional Resources:

Erik Demaine's lecture on Computational Complexity (MIT)

31 questions
40
votes
4 answers

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 idea about how they find the time complexity of…
user9947
10
votes
1 answer

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
  • 103
  • 1
  • 6
7
votes
2 answers

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 suspect that there are only approximate solutions…
Gottfried William
  • 343
  • 1
  • 11
4
votes
0 answers

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)$?

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 computational complexity of the forward pass of a…
Jonathan Azpur
  • 113
  • 3
4
votes
1 answer

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: for o in my_graph.getDerivedObjects(): if hasPropertyX(o): process(o) break; If one of the derived objects has…
Guillermo Mosse
  • 327
  • 1
  • 10
3
votes
1 answer

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|^{2}|A|)$, where $|S|$ is the number of states…
Shifat E Arman
  • 83
  • 1
  • 5
3
votes
0 answers

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 processed in the well known convolutional neural…
Ivan Talalaev
  • 131
  • 2
3
votes
1 answer

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 some of the methods that could be used: Presumably,…
Ron Germano
  • 33
  • 4
3
votes
0 answers

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 algorithms are calculated, however, with the…
rahul tomar
  • 51
  • 4
3
votes
2 answers

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 GBFS similar to DFS. It expands the whole branches…
iRestMyCaseYourHonor
  • 141
  • 1
  • 6
2
votes
1 answer

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 algorithm for the shortest path problem in a graph?
Questioner
  • 283
  • 1
  • 10
2
votes
1 answer

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 \lor x_2) \land (x_3 \lor x_1)$$ I reduced it to…
xava
  • 423
  • 1
  • 3
  • 9
2
votes
1 answer

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, but I never saw any papers similar to this. i.e…
thecomplexitytheorist
  • 766
  • 3
  • 19
2
votes
2 answers

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{C^*/\epsilon}\rfloor}), $$ where $b$ is the…
user153245
  • 123
  • 8
2
votes
0 answers

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 algorithm it's natural to attempt to define a notion…
FoundABetterName
  • 71
  • 7
1
2 3