Tagged Questions

The tag has no usage guidance.

48 views

How much variance is captured by the RFF maps? [migrated]

The RFF maps here are possibly the most used feature maps. I was wondering if there are cases where anyone has theoretically estimated the total variance captured by these maps? Is any simplification ...
117 views

Most efficient inplace merge algorithms (stable and unstable)

I am currently researching the best algorithms available to achieve an inplace merge operation: consider two consecutive sorted arrays of size n and ...
443 views

Random walk and mean hitting time in a simple undirected graph

Let $G=(V,E)$ be a simple undirected graph on $n$ vertices and $m$ edges. I'm trying to determine the expected running time of Wilson's algorithm for generating a random spanning tree of $G$. There, ...
108 views

Complexity analysis on a parameterized recurrence relation

In order to analyse the complexity of our algorithm, we try to solve this recurrence: $T(n)=3T(n-1)-T(n-2)+T(n-k)+3^k$ ; in which $k$ is a parameter to be fixed. We know that this kind of ...
173 views

How to treat dynamic memory allocation in algorithm analysis?

I have an algorithm in which I want to dynamically allocate some memory. Let's say that I have N numbers and that I want to describe some binary relation over them. To do so I want to create a N*N ...
384 views

Travelling sales man with Quantum Computers [closed]

I know that it takes billions of years to solve the travelling sales man when n = 25 (Number of cities). I am wondering how fast can a quantum computer solve the travelling sales man problem (for ...