# Tagged Questions

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

0answers
16 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?
0answers
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
0answers
9 views

### Standard methods for self-consistent field theory

I'm attempting to replicate a neural-network model that comprises the following self-consistent equation: $$R(x_i)=\bigg[I_s(x_i)+I_A(x_i)+\frac{1}{N}\sum^N_{j=1}J(x_i-x_j)R(x_j)-T\bigg]_+$$ The ...
0answers
10 views

### Estimate the complexity for number times the function n/ lgn will be called recursively such that the result is a constant c = 2?

Cormen exercise $3.6$ which defines recursive function $f(i)$ such that $i$, $i \ge 0$ and the function is recursively called on itself $f(….f(i))$ such that it reaches a constant $c= 2$. Please help....
1answer
49 views

### derivation of fibonacci log(n) time sequence

I was trying to derive following equation to compute the nth fibonacci number in O(log(n)) time. F(2n) = (2*F(n-1) + F(n)) * F(n) which i found on wiki form the ...
1answer
50 views

### Help to solve Divide and Conquer

How can I solve the following Divide and Conquer example? If you don't have enough time please just tell me the idea? Thanks $$T(n)=T\left(\frac{n}{7}\right)+T\left(\frac{11n}{14}\right)+n$$
0answers
28 views

### Doesn't the recursive Fast Fourier Transform violate f(-x) =/= f(x) for odd functions?

When you recursively split into $Y_{even}$ and $Y_{odd}$, from the second recursion onwards don't these sets have their even-ness and odd-ness violated? I.e., assume you are running the FFT algorithm ...
1answer
37 views

### Algorithm to order and partition a set of of (n,m) pairs with constraints.

I ran into this problem while looking at Google API distance matrix service. Say you have a collection of a few million (origins, destinations) unique pairs/2 column table like (address, zip) for ...
0answers
34 views

### recursive least squares for nearly singular matrices

I have an image reconstruction problem which I want to solve as a linear system $Ax=y$. A matrix is big, but for the beginning I can shrink the imaging region to $nPix$ = 2000 pixels. number of ...
2answers
30 views

### Finding Recursive formula for value of a game

I understand the value of the game changes depending on what pile I take the coin from. If I take a coin from the front, I get $i+1$ coins (if I take $i = 1$, now $i =2$). This happens until $i = j$ ...
0answers
56 views

### Find a polynomial such that this proposed root finding algorithm fails.

Is this polynomial root finding algorithm below known, and under what conditions for the choice of polynomial coefficients does it find at least one root? Description of the algorithm: Consider the ...
1answer
54 views

### Union, intersection, set theoretic difference of recursively enumerable sets

Forgive me for asking though some of this has been asked/answered elsewhere and there are many examples on the internet; I ask again because I am doing a Maths course (not computer science) and we don'...
0answers
17 views

1answer
22 views

### Is the set of numbers of computable functions f(x) = c recursively enumerable?

Consider the set of numbers of computable functions such that is $f(x)$ defined, $f(x) = c$ for any $x$. Is this set enumerable or co-enumerable? (Or neither). A bit of my thoughts on it. We can take ...
2answers
253 views

### Solving the Recurrence Relation/Series fn = 1 + fn-1*(M) where M is a constant

So I'm trying to solve this week's FiveThirtyEight Riddler. In a building’s lobby, some number (N) of people get on an elevator that goes to some number (M) of floors. There may be more people ...
1answer
31 views

0answers
25 views

### Why FFT algorithm (Cooley-Tukey) takes O(nlogn)?

I was wondering how this algorithm can be formally interpreted with an upper bound n*log(n). There's some formal proof for this? I would appreciate if somebody can help me. Thank you.
0answers
57 views

Given positive integers $n$ and $m$, count the $m$-subsets $S\subseteq[2^n - 1]$ such that the bitwise XOR of the members of $S$ is $0$, where as usual for any positive integer $k$ we let $[k]=\{1,2,\... 2answers 66 views ### Define algorithm using divide and conquer paradigm [closed] Q:Describe a Θ(n lg n)-time algorithm that, given a set S of n integers, determines which two elements in S have the smallest difference. (From what i understand, we first apply merge sort to our ... 2answers 88 views ### A square root solving algorithm invented by my friend Recently, my friend told me a square root algorithm: $$\left\{ \begin{array}{lll} p_{n+1}&=&p_n+aq_n \\ q_{n+1}&=&p_n+q_n\end{array}\right.$$ Finally,$p_n/q_n$is near$\sqrt{a}$. ... 0answers 17 views ### recurrence algorithm unfolding with answer, need explanation SO the question is to prove$O(n\log n)$hence figure out$f(n)$correct? why does$n = 2^{2^k}$what is so special about$2^{2^k}$can i use another number? this answer is using substitution? I don'... 2answers 52 views ### recurrence algorithms, algebra issues? So we're given a problem to solve... no other instructions.. the answer is given as well. I am having trouble understanding how this problem is unrolled. I understand that$\sqrt{2^{2^k}}$can ... 1answer 31 views ### Proving$T(n) = T(n-2) + \log_2 n$to be$\Omega(n\log_2 n)$As title, for this recursive function$T(n) = T(n-2) + \log_2 n$, I worked out how to prove that it belongs to$O(n\log n)$; however I'm having trouble proving it to be also$\Omega(n\log n)$, i.e. ... 0answers 13 views ### Finding the Reccurrence of a Periodic Sorting Network Consider this Periodic Network of input size$n = 8$. I am trying to find an asymptotic approximation of the size (# of comparators) for such network. My attempt: Since there are$n$inputs, there ... 2answers 30 views ### Not understanding the steps in Simplifying a Series I am hoping someone can explain why the second step has a $$o(\lg^k{n})$$ and then in the next step how the Riemann sum is simplified and the change of sign. $$B = \sum_{j=0}^{\log_b{n}-1}\lg^k\frac{... 1answer 46 views ### Recurrence relation with ternary strings Express, as a recurrence relation, the number of ternary strings of length n that contain either 2 consecutive 0's or 2 consecutive 2's. Don't forget to include the base case. Can someone help me ... 1answer 56 views ### Recursive Sum of Previous Term and its Inverse Can anyone help me with finding a closed form for F_n where$$F_0=x_0F_{n+1}=F_n+\frac{1}{F_n}=\frac{F_n^2+1}{F_n}$$I could imagine this already having been done, in which case I'd appreciate ... 0answers 66 views ### How to solve recurrence$T(n) = T(n/3) + T(2n/3) +n\$ using Master Theorem

I'm trying to solve the following recurrence using Master Theorem, but I'm not used to seeing recurrences with to terms ( i.e. T(n)) for the cost of operations. I'm pretty sure that a should be 1 and ...