# Tagged Questions

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

25 views

### Recursive formula in term of original value

$$P_1=P_0G_{0,1}A_1\\ P_m=P_{m-1}G_{m-1,m}A_m+A_0\sum_{i=0}^{m-2}P_i G_{i,m}~~\text{for}~~m\geq 2$$ Is it possible to write $P_m$ in terms of only $P_0$, i.e., without other $P_j$ terms?
34 views

### Show that $\pi$ is a primitive recursive number [on hold]

Can anyone provide a proof that $\pi$ is a primitive recursive number, or suggest how I might prove it? Thanks
411 views

### Help Solve Recurrence Relation T(n) = 3T(n/2) + O(n)

Given recurrence $$T(n) = 3T(n/2) + O(n)$$ $$let\:cn >= O(n)$$ for some constant c I can bound $$T(n)$$ in terms of $$T(n/2)$$ so I have $$T(n) <= 3T(n/2)+cn, \ \ \ \ \ k = 1 \ call$$ So I ...
625 views

11 views

### Is there a better way to get the value of X after recursively multiplying by list Z?

If I have a number X and a list of percentages Z, how would I find the value of X after repeatedly multiplying it (and its result) by each percentage value in the list Z? Naive Way: ...
6k views

### Convert Recursive to Closed Formula

I got a particular sequence defined by the following recursive function: $$T_n = T_{n-1} \times 2 - T_{n-10}$$ I need help converting it to a closed form so I can calculate very large values of n ...
27 views

### What are the first three values for the following recursive sequence?

$a_0 = 3$ $a_n = (a_{n-1})^2 + (a_{n-2})^2 +\cdots + (a_0)^2$ for all integers $n\geq 1$. Would that mean $a_1 = a_0^2 = 9$? Thanks!
28 views

55 views

### Asymptotic equalities in master theorem proof

In all proofs of master theorem I've found so far (Cormen et al., also here http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec19-master/mm-proof.pdf), there is essentially a following series ...
46 views

### Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than $2$ I should choose a special partitioning hyperplane for the divide and conquer algorithm to get $O(n \log n)$. I am confused because to choose this ...
21 views

### Compute smoothed probabilities for EM algorithm

In order to compute the expected value of log-likelihood in EM algorithm, we use 3 different probabilities Forecast (predictive) probabilities Inference probabilities Smoothed probabilities ...
27 views

### How does this self referencing (circular reference) equation terminate (i.e. not create a paradox?)

I'm working with a financial equation which seems like it should result in a paradox but I'm told doesn't, however I haven't been told why it doesn't. (I don't work in the field I'm a programmer ...
38 views

### Write a recursive algorithm for locating the max number amongst k integers.

Iteratively, I know how to find the max number: Set Max = List[0], for k in range(len(List)), if List[k] > Max, Max = List[k]. Return Max. Recursively, I'm not quite sure. Here is my idea: I ...
25 views

20 views

### Find a function f(n) such that T(n) is $\Theta(n \cdot log(n))$

Find a function f(n) such that $T(n)=16 \cdot T(\frac{n}{4}) + f(n) = \Theta(n \cdot log(n))$ Also, another section of the question is where $T(n) = \Theta(n^{2})$ I've tried using the master ...
29 views

### How is this recursion for horizontally convex polyominoes clear according to author?

How is the recursion $a(m,n)$ clear? I don't understand how this is clear.
29 views

### Contour and perimeter recognition in binary image

I need to detect contour (object) and find the perimeter of a detected object. For example, I have the following image: http://i.stack.imgur.com/40TTX.png All images are binary, so they consist of ...
47 views

### Prove a Recursive Formula by Induction?

So I have a bonus question on a homework assignment I am working on that literally just asks "How would you prove a recursive formula by induction?" There are no numbers, or sequences given. I ...
52 views

### Recursive approach for computing $(a,b) \mapsto a^b$

As a programming exercise I was asked to implement a recursive approach for computing $a^b$ given two real $a,b \in \mathbb R, a>0$. I assume this task has a typo, as a recursive approach makes ...
Let be $a_{0}=1,a_{1}=1,a_{n}=4a_{n-1}-2a_{n-2}$ if($n\ge 2)$ Should I first find the generating function of the recursion and after that? I solved it with Wolfram Alpha and after it the result is \$\...