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

learn more… | top users | synonyms

0
votes
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?
0
votes
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
0
votes
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 ...
0
votes
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....
1
vote
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 ...
0
votes
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$$
0
votes
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 ...
-1
votes
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 ...
0
votes
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 ...
0
votes
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$ ...
0
votes
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 ...
1
vote
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'...
0
votes
0answers
17 views

Stuck: To show that the divide and conquer relation represent Merge Sort

I've just started with recurrence relations. I know that the divide and conquer relation in merge sort is given by, $M(n) = 2M(n/2) + n$ Question: A divide and conquer relation is given $$a_n = ...
1
vote
1answer
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: ...
1
vote
0answers
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!
0
votes
0answers
28 views

Solving a recurrence relation using a subtitution method $T(n+1)=T(\frac {n} {2} )+ \Theta\left(n^2 \right) $

I got stuck when I want to solve this recursive relations by substitution $$ T(n+1)=T(\frac {n} {2} )+ \Theta\left(n^2 \right) . $$ $$ T(n+1)=2 T(\frac {n} {2} )+ \Theta\left(n\right) . $$ $$ T(n)=T(\...
1
vote
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 ...
0
votes
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 ...
1
vote
1answer
31 views

If $T(n)=T({n\over 3})+T({2n\over 3})+n$ then $T(n)=O(n\log n) $. How is the upper bound achieved?

Trying to show that if $T(n)=T({n\over 3})+T({2n\over 3})+n$ then $T(n)=O(n\log n) $ using a tree, I do know that taking the shortest path gives a lower bound of the number of steps equivalent to $n\...
0
votes
2answers
47 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
0
votes
1answer
20 views

Is it possible to solve a recurrence with max()?

I have the following problem. Imagine there is a set $P=\{p_1,p_2,p_3\} \subset \mathbb Z $ and I want to describe how it changes in time. Informally, the rule is simple: At every time-step, subtract ...
0
votes
0answers
24 views

Runtime of Algorithms (Recurrence&Induction)

Two algorithms are given: $$T_A(n) = (\log_4(n) + 1) \cdot n\quad\text{and}\quad T_B(n) = 4 T_B\left(\frac{n}{4}\right) + n^\alpha$$ $$T_B(1) = 1; \alpha \in \mathbb R_+; n = 4^k\quad\text{...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
45 views

Algorithm for the independent domination number

A dominating set for a graph $G = (V, E)$ is a subset $D$ of $V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number $γ(G)$ is the number of vertices in ...
0
votes
3answers
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 ...
1
vote
1answer
25 views

Algorithm for generating all elements of a set consisting of specific $n$-tuples

I was working on functional analysis last night, and then my mind got distracted by the following problem. Consider a set $$I=\{0,1\}$$Now consider a subset of $\mathbb{R^n}$ $$X=\{(x_1,x_2,\dots ,x_n)...
0
votes
1answer
44 views

Recursive Definitions

I have two recursive definitions that I need to determine if they are correct. The first one is: The set S of all positive integer multipliers of 5 can be described by the following recursive ...
0
votes
0answers
35 views

Iterative methods to find roots

I'm trying to do optional exercises for my numerical methods class. I'm stuck in this one right now: Consider the function $f(x)=-e^{-2x}+3x$. a) Prove that $f$ has an unique real root. ...
0
votes
1answer
17 views

Branching/layered optimisation - how?

Imagine you had a collection of systems each with their own constraints and objective functions to optimise (likely similar in form to each other), these then collectively aggregated into a 'super-...
0
votes
2answers
28 views

Recursive type for $ y_{k}=2^k\tan(\frac{\pi}{2^k})$

Given the sequence $ y_{k}=2^k\tan(\frac{\pi}{2^k})$ for k=2,3,.. prove that $ y_{k} $ is recursively produced by the algorithm: $$ y_{k+1}=2^{2k+1}\frac{\sqrt{1+(2^{-k}y_{k})^2}-1}{y_{k}} $$ for k=2,...
1
vote
1answer
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 ...
1
vote
1answer
29 views
0
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
21 views

Implementing Recursive descent algorithm for PWL Approximation

I am currently trying to linearise a convex function at hand (an M/M/1 curve) using piecewise linear functions. Since I wanted the approximation error to be as low as possible, I searched for some ...
0
votes
1answer
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 ...
1
vote
2answers
28 views

How can I solve this linear recursion?

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 $\...
0
votes
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.
3
votes
0answers
57 views

Count number of m-subsets with xor = 0 [closed]

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,\...
0
votes
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 ...
2
votes
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}$. ...
0
votes
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'...
1
vote
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 ...
2
votes
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. ...
0
votes
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 ...
0
votes
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{...
0
votes
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 ...
4
votes
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_0$$ $$F_{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 ...
0
votes
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 ...