# Tagged Questions

Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.

30 views

### Getting rid of $2^n$ when solving $a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ by characteristic roots

$a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ For $n\ge3$, With initial conditions $a_2=1$, $a_1=1$, and $a_0=1$ I'd like the find the particular solution with characteristic roots. However when generating ...
41 views

30 views

### Does this recurrence relation run in $\Theta(n)$?

This is the recurrence relation I am trying to solve: \begin{align} T(n) & = 2 \cdot T \left( \frac{n}{4} \right) + 16, \\ T(1) & = c. \end{align} I broke this down (i.e., solved this ...
282 views

### How to find a enclosed envelope with maximum points among a cloud of spheres? [ Concave Hull ]

I have a questions regarding the selection of the outer points (i.e. sphere center), among a collection of many spheres in 2D/3D space. The outer points is that when all of these points are ...
50 views

### Proving a recursive algorithm on a set is true

If I have an algorithm that returns the entry of a set with the largest value, how do I prove the algorithm is true mathematically? (I know I could just write tests for it.) I understand how to use ...
63 views

### Find a shortest way between nodes in graph

I have a next structure : Each node in graph may have more than 2 links. I want to find a shortest way with node 1 and 13. ...
53 views

### Edited-How can I solve polynomial recurrences like $f(n+1)=\frac{2f(n)}{f(n)+1}$

Can anybody tell me the systematic way of solving this recurrence. $$f(n+1)=\frac{2f(n)}{f(n)+1}$$ I looked over the internet, but could not find the answer. Thanks {Edit- I am sorry, previously I ...
31 views

### Uniqueness of abelian group structure on a given set and recursive algorithms

If we have some function $f$ under $\mathbb{Z}$ and $$f(a, f(b, c)) = f(f(a, b), c)$$ $$f(a, b) = f(b, a)$$ $$f(a, 0) = a$$ $$f(a, -a) = 0$$ meaning $f$ is an abelian group with an identity element of ...
198 views

### How page rank relates to the power iteration method

I do not see how pageRank relates to the power method. Since for the pageRank we are looking for the steady stable state (vector) for a Markov (transition) matrix and the matrix has already an ...