# Tagged Questions

The tag has no usage guidance.

76 views

### What does $\tilde O(nm)$ mean?

I know that $\tilde O(n)$ means $O(n*(logn)^k)$ for some k. But what about when you have two parameters n, m? Would it mean $O(nm*(log(nm))^k)$ or $O(nm*(logn)^{k_1}*(logm)^{k_2})$ for some $k_1, k_2$?...
118 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 ...
462 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, ...
110 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 ...
436 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 ...