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

learn more… | top users | synonyms

0
votes
1answer
36 views

Proof by induction for a recursive function

Really having a tough time doing this question: Consider the function $\operatorname{f}: \Bbb N \to \Bbb N$ defined recursively as follows: 1) Base case: $\operatorname{f}(0) = 0$ 2) Recursive ...
0
votes
3answers
525 views

Counting arrays with gcd 1

I want to calculate the number of arrays of size $N$, such that for each of it's element $A_i, 1 \leq A_i \leq M$ holds, and gcd of elements of array is 1. Constraints: $1 \leq A_i \leq M$ and $A_i$ ...
1
vote
4answers
144 views

Prove that the Fibonacci recursion diverges

I have this sequence with $ n \in \mathbb{N} $ $ f(1) = f(2) = 1 $ and $ f(n) = f(n-1) + f(n-2) $ for $n \ge 3$ I think this sequence is bounded below and unbounded above. So it's clear that this ...
0
votes
3answers
63 views

Constructing a recursive sequence that converges to sqrt 17

One of the problems that we have for abstract math is the following: Using the recursive sequence definition, construct a sequence that converges to $\sqrt{17}$. It is my understanding that the ...
3
votes
1answer
130 views

All solutions of the recurrence relation

Find all solutions of the recurrence relation $$ a_n = 2a_{n-1}+15a_{n-219}-64a_{n-3}+k $$
0
votes
1answer
34 views

Explicit (General) formula for recursive definition.

I am given $a_n=3a_{n-1}+4^n$, $n=1,2,3,....$ and $a_0=1$. First four terms: $$ \begin{align} a_1&=3.1+4^1=3+4=7\\ a_2&=3.7 + 4^2 = 21 + 16 = 37 \\ a_3&=3.37 + 4^3 = 111 + 64 = 175\\ ...
0
votes
1answer
33 views

Solving time complexity of merge sort

I was asked to prove that the time complexity of merge sort is $ O(log_2n)$ but I cannot find a way to continue my method. Any help? $T(n)=2T(\frac{n}{2} )+n$ $T(n)= 2[2T(\frac{n}{4})+n] +n = ...
0
votes
1answer
22 views

Log property in proof of Master theorem

The family of recurrence considered is of the form $$ T(n) = aT(n/b) + n^c $$ $a,b,c$ are integers. One case of master theorem states: if $c< log_b a$, then $T(n) = \Theta(n^{log_b a}) $. I have ...
3
votes
2answers
118 views

Finding the convergent value of a recursion similar to Arithmetic-Geometric Mean recursion

The sequence is defined as follows : Start : $(x_0,y_0)$ with $ 0 < x_0 < y_0 $ Step : $x_{n+1} = \frac {x_n+y_n} {2}$ , $y_{n+1}= \sqrt{x_{n+1}y_n} $ Find $\lim_{n\to \infty}(x_n,y_n)$ . ...
2
votes
4answers
49 views

Find exact closed form of recurrence $g(0) = 0, g(1) = 3, g(n) = g(n − 1) + 2g(n − 2)$ for $ n \geq 2$

$g(0) = 0, g(1) = 3, g(n) = g(n − 1) + 2g(n − 2)$ for $n \geq 2$ Our lecture notes suggest us to work backwards until you get the first term, i.e. $g(1)$ I am not quite sure how that works as the ...
1
vote
0answers
59 views

Help me generalize what this divisor transform does.

I have an algorithm which takes as input the series expansion of: $$\frac{-(1 + ax(-2 + x + ax))}{-1 + ax} \tag 1$$ or expressed differently: ...
0
votes
0answers
17 views

Breadth First Search - Building All Possible Trees of a Set

Suppose there is a set of values arranged in a binary search tree (BST). I'm trying to write an algorithm that takes in a sequence, and prints all permutations (BSTs) that have that sequence as their ...
1
vote
0answers
76 views

Trace and transpose of a Matrix

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1 =sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2} =\frac{s}{n+2}\{ R_{n+1} ...
0
votes
1answer
59 views

A Difficult Recursive Equation

I've got a recursive equation of the form $$ x_{n+1} - x_{n} = \frac{(-1)^n}{2 \cdot 4 \cdot 6 \cdot ... \cdot 2n}(x_0-x_1)$$ for $n \geq 2$. We can assume $x_0$ and $x_1$ are just real numbers/ I ...
1
vote
3answers
20 views

running time of an algorithm

I am trying to prove an algorithm with input size $n$ satisties the recurence relation (for $n>=1$) $T(n) = T(n-1)+n$ and an initial condition of $T(1)=1$ has running time in $Θ(n^2$). By using ...
1
vote
0answers
30 views

Solution of ODE with initial values

Given data in the problem ${\psi'(t)}_{3 \times 3}=A_{3 \times 3}\psi(t)_{3 \times 3}, \psi(0)_{3 \times 3}=R^{cl}_{3 \times 3} \\ \phi'(t)_{3 \times 3}=t\hspace{.1cm}B_{3 \times 3} \phi(t)_{3 ...
0
votes
1answer
30 views

$T(n)=T(n-1)+O(\log n)$ is $T(n)=O(n^2)$ or $T(n)=O(n \log n)$

I have this Recurrence relation: $T(n)=T(n-1)+O(\log n)$ What is the solution? $T(n)=O(n^2)$ or $T(n)=O(n \log n)$ What I did is: I assume that $T(n)\le O(n^2)$ And that's bring me to $O(n^2)$, ...
2
votes
2answers
71 views

Towers of Hanoi Starting From Initial (Legal) Configuration?

I was recently asked in an interview how an algorithm for solving the classic Towers of Hanoi problem would differ if you were given an initial (legal) configuration of the towers, and had to start ...
1
vote
3answers
51 views

recursive to explicit sequence

I am trying to find the explicit formula for the following recursion: $$a_{1}=3,\quad a_{n}=3- \frac{1}{a_{n-1}},\quad n \in \mathbb N,n>1$$ I tried in many ways but I cannot find any ...
1
vote
1answer
24 views

Algorithm Running Time

Given an algorithm with a running time $$T(n)=5T(n/2)+n^2$$ So the number of nodes at a depth $i$ would be: $5^i$ The input size for each node at $i$ would be: $n/2^i$ Agreed. Then it states that ...
4
votes
1answer
225 views

How many distinct ways to climb stairs in 1 or 2 steps at a time? (Fibonacci puzzle)

There is a very interesting puzzle for fibonacci sequence ...
0
votes
1answer
33 views

How to find if an array has at least 10 unique integers in $O(\log n)$?

I am given a sorted array of integers. I want to find out if the array has at least 10 unique integers. I know this can easily be done with an algorithm that runs in $O(n)$ simply by going through ...
1
vote
0answers
36 views

Finding the explicit form of the recursive function $P_{1(n)}=\left\lceil\frac12P_{1(n-1)}\right\rceil+\left\lfloor\frac12P_{2(n-1)}\right\rfloor$

I'm trying to find the explicit form of the recursive function $$P_{1(n)}=\left\lceil\frac12P_{1(n-1)}\right\rceil+\left\lfloor\frac12P_{2(n-1)}\right\rfloor\;.$$ First, let me explain what this ...
2
votes
5answers
138 views

How to give a good guess to the recurrence relation problem [duplicate]

I have been trying to solve the following recurrence relation $$T(n)=2T(\frac{n}{2}) + nlgn$$ by using substitution method. I started to compute $T(1)$ ,$T(4)$,$T(8)$,$T(16)$ to guess a solution as ...
1
vote
2answers
43 views

Optimal Number of White Balls

There are C containers, B black balls and infinite number of white balls. Each container should have at least one ball. Each of the containers may contain any number of black and white balls. Action ...
1
vote
0answers
42 views

Recurrence Derivative

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1(s)=sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2}(s)=\frac{s}{n+2}\{ ...
1
vote
1answer
156 views

Generate all permutations of a string containing repeated characters

I was writing a program to print all the permutations of a string. I came up with the following: ...
0
votes
0answers
22 views

Binary Search when no “fixed” answer…? (Font Sizing)

So I'm trying to figure out how best to implement a binary search algorithm to find the "optimal" font size for a piece of text to fit into a given space, to the nearest 0.5pt. My understanding is ...
0
votes
1answer
20 views

Recurence Problem. - Solve either by substitution or Expansion

Function T(n) is defined by the following recurrence relation: $$ T(n)=2T(\lfloor\sqrt{ n}\rfloor)+\log(n) $$ $$ T(0)=1 $$ How would I Solve by substitution and/or Expansion? Note: ...
1
vote
1answer
91 views

Using Extended Euclidean Algorithm for $85$ and $45$

Apply the Extended Euclidean Algorithm of back-substitution to find the value of $\gcd(85, 45)$ and to express $\gcd(85, 45)$ in the form $85x + 45y$ for a pair of integers $x$ and $y$. I have ...
0
votes
2answers
49 views

A nice recurrence sequence

I want to find general solution for recurrence: $a_n=7a_{n-1}-10a_{n-2}+4n$ with suppose $c_1, c_2, c_3$ is constant. I need some tutorial or solution on this challenging recurrence.
0
votes
0answers
23 views

find the explicit form of recursive equation: $p_{n+1} = 3.4(1-p_n)p_n $

I'm trying to find the explicit form of recursive equation: $p_{n+1} = 3.4(1-p_n)p_n $ I can do this pretty easily using matrix iteration for linear equations, but I'm completely lost how to do ...
1
vote
1answer
60 views

Solving recurrence equations with repeated substitution?

Say we have a recurrence equation as $$ T(n) = \begin{cases} T\left(\frac n2\right) +n & \text{if }n\ge2 \\ 1 & \text{if }n=1 \end{cases} $$ Would the first substitution be like this? ...
3
votes
1answer
48 views

Solving recurrence -varying coefficient

How can one find a closed form for the following recurrence? $$r_n=a\cdot r_{n-1}+b\cdot (n-1)\cdot r_{n-2}\tag 1$$ (where $a,b,A_0,A_1$ are constants and $r_0=A_0,r_1=A_1$) If the $(n-1)$ was not ...
0
votes
1answer
92 views

Karatsuba multiplication algorithm of two 6 digit decimal numbers.

What are the min and max number of single digit multiplications, involved in recursive karatsubha multiplication of two 6 digit decimal numbers? I found different results on different numbers. But I ...
0
votes
1answer
96 views

Improving the Edit Distance Algorithm

I applied an Edit Distance Algorithm for similarity between two strings over the lowercase latin alphabet, where the first string has length $m$ and the second length $n$. However I want to improve ...
0
votes
1answer
66 views

Any way to get a Recursive function from its closed form?

For an exercise, the goal is to find a recursive definition for a certain function. the function itself is as follows: f(a,b) is the # of binary strings of length a and with b more 1s than 0s. eg: ...
0
votes
1answer
26 views

A recurrence equation for the number of multiplications in an algorithm for computing powers

We were asked the to find the recurrence equation for the number of multiplications for the following algorithm as a function of N. For simiplicity, let $ N = 2^k $ and is a positive integer: I ...
1
vote
1answer
101 views

Find a Recurrence Relation

I want to find a recurrence relation for number of decimal numbers with length n, (we called $a_0$ ) that not includes 0 and any combination of 11,12, 21. i see the result is: ...
0
votes
1answer
35 views

Geometric sum of recurrence relation

I am reading the textbook Algorithm Design by Kleignberg and Tardos and I am having trouble on page 216. $$T(n) \le \sum_{j=0}^{log_2n - 1} \left ( \frac{q}{2}\right )^j cn = cn \sum_{j=0}^{log_2n - ...
2
votes
2answers
67 views

Recurrence Relation from Old Exam

I see this challenging recurrence relation that has a solution of $T^2(n)=\theta (n^2)$. anyone could solve it for me? how get it? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 ...
1
vote
0answers
33 views

Need help checking my recurrence for a simple algorithm

All I'm writing to get a second opinion on the algorithm shown in this link. I'm pretty sure its supposed to be $T(n)=2T(n/2)+n$ but I can't see where I'm supposed to get the +n from. So far I'm ...
0
votes
1answer
108 views

recursive equation: divide and conquer, subtract and conquer problem in one

I have a recursive equation that does not apply to the master method, since there is subtraction in the equation. I'd like to use the substitution method, but I have no idea where to start. Could ...
0
votes
1answer
29 views

Proving the correctness of a program

So I have this program below SquareRootRecursion that I need to prove is correct. However i'm not sure what it's pre and post conditions would be and how I would use those to prove it's correctness. ...
3
votes
2answers
69 views

Proof of recursivity of Shannon's Entropy

Does anybody know a book where the proof of recursivity property of Shannon's Entropy can be found? I mean this: $$H(q_1,...,q_n)=H(q_1 + q_2, q_3,...,q_n) + (q_1 +q_2)H( \frac{q_1}{q_1+q_2} , ...
0
votes
1answer
41 views

How to solve a recurrence

Apologies for this is a really trivial question, but I cannot figure out what to do after understanding the pattern of the function. Say I have this: $\begin{align} T(n) & = T(n-1) + 1/n \\ ...
1
vote
1answer
186 views

What are algorithm? Can we relate algorithm using set theory concepts?

What really algorithm are? Can we define algorithm as functions or in terms of set theory Can we reconvert proof using algorithm in set theory concept.For example, Theorem: A function defined on ...
1
vote
2answers
47 views

Recurrence equation of $ T(n) = T(n/2 ) + dn\log_2(n)$

I have the following equation: $$T(n) = T\left({n \over 2}\right) + d n \log_2 n$$ A little investigation: $T(2^1) = 1 + 2d$ $T(2^2) = T(2^1) + 2^2d\times 2 = 1 + 10d$ $T(2^3) = T(2^2) + ...
3
votes
0answers
41 views

What's the next “recursion” here?

Plotting a single 3d helix is x = cos(t); y = sin(t); z = t; From this equation: x = [R + a cos(\omega t)] cos t y = [R + a cos(\omega t)] sin t z = h t + a sin(omega t) Comes the awesome ...
1
vote
2answers
417 views

Algorithm to calculate rating based on multiple reviews (using both review score and quantity)

First of all I must state that I am not a mathematician, so please correct me if I use wrong terminology. I am building a web application which needs to calculate the rating for each entity based on ...