# Questions tagged [time-complexity]

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

12 questions
Filter by
Sorted by
Tagged with
31 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 ...
24 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 ...
30 views

### Prove that in such cases, it is possible to ﬁnd 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 classiﬁcation. Assume that there is a learning algorithm that implements the ERM rule in the realizable case such that the ...
283 views

### What is the time complexity of the forward pass algorithm of a 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?
66 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 ...
52 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: ...
117 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 ...