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

learn more… | top users | synonyms

1
vote
0answers
41 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
153 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
51 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
47 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
331 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
24 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
22 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
105 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
53 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.
1
vote
1answer
236 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? ...
4
votes
1answer
57 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
152 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
125 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
109 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
30 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
105 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
45 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 - ...
3
votes
2answers
76 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
38 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
256 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
33 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. ...
4
votes
2answers
116 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
45 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
203 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
69 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
43 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
1k 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 ...
1
vote
1answer
39 views

Finding a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$

Can the master theorem be used to prove a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$? I've drawn the tree for the recurrence and found a sequence: $n + 2n + ...
1
vote
1answer
42 views

How can I solve the particular solution of the following recurrence (recursive) relation?

Having $a_n = 3a_{n-1} + 2a_{n-2} + 3·2^{2n-1}$ $a_1 = 12$ $a_0 = 0$ I solved the homogeneous part and got: $a^{{h}}_n = 1/12·2^n - 1/12·1^n$ This is the particular solution that I need to ...
1
vote
0answers
180 views

Using a Recursion Tree to solve the recurrence $T(n) = \sqrt n T(\frac{n}{2}) + 10n$?

I am attempting to solve the above recurence by giving tight $\Theta$ bounds. Assume that the logs here are all base 2! To solve a recursion tree as far as I understand, I need two things. The ...
1
vote
0answers
116 views

Algorithms recurrence equation using unwinding / substitution

This is homework for introduction to Algorithms this is what I have below. (25 pts) Use the direct unwinding to prove that the recurrence equation T(n)= 2T(n/2)+ nlogn has a lower bound of ...
0
votes
1answer
45 views

Recurrence Relation

So I am just making sure I am on the right track with this. I have the recurrence: T(n) = 2T(n-2) + 1 I am trying to solve this recurrence to get the time complexity T(n) = 2(2T(n-4) + 1) + 1 T(n) ...
1
vote
1answer
38 views

Question about Growth Rates

I see in some notes from my instructor in Algorithm course that $\Sigma_{i=0}^{log n} (n/2^i)$ has growth bigger than $\Sigma_{i=1}^{n} (i log i)$. i couldn't understand why? any tutorial or hint?
5
votes
0answers
121 views

Is there a simplification for the coefficients generated with the Mandelbrot iteration rule?

The Mandelbrot Set is obtained using the equation $z_n=z_{n-1}^2+c$ for some constant $c \in \mathbb{C}$ with $z_0=0$. Therefore, $z_1=c$, $z_2=c^2+c$, $z_3=c^4+2c^3+c^2+c$, etc. I have a function ...
0
votes
1answer
37 views

recursive sequence - Which approach can I take to solve this equation?

Having this recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 4·3^n$ $a_1 = 36$ $a_0 = 0$ How can I solve this? I tried by characteristics roots and got stuck: *making $a_n=r^n$ $r^n = 5r^{n-1} - ...
1
vote
2answers
109 views

Can this recursive summation function be simplified?

I have the recursive function $$ a_n = \sum_{x=1}^n a_{n-x} a_{x-1} $$ where $a_0=1$ and $n$ is a positive integer. Looking at a graph of this function, it's very exponential in form, but it's not ...
0
votes
1answer
1k views

Tight asymptotic upper and lower bounds

I have a equation: $T(n) = 4T(n/3) + n\ln n$ In this equation, I have to give tight asymptotic upper and lower bounds. What does that mean? I know I can apply Master theorem (which gives me theta ...
1
vote
1answer
137 views

Big O complexity of the partition function derived from this code?

I am not able to calculate the Big O complexity of the partition function given in the code below. I tried to calculate it by estimating the number of nodes in the tree. So far, I've figured out that ...
2
votes
1answer
34 views

How to solve the recursive complexity?

I have such recursive complexity $T(n) = T(n-2) + log(n)$. The problem is that I cant use a recursion tree or the master theorem. The only way, which I know, is to guess and then proof the answer. ...
1
vote
1answer
69 views

Quicksort probabilistic analysis

Let us say that we randomly pick up a pivot element and partition the array around it. What is the probability that we always pick the pivots in subsequent recursive calls such that it partitions the ...
1
vote
1answer
33 views

limit of $f_n(a) = a^{f_{n-1}(a)}$ as $n$ approaches infinty for small values of $a$

So a friend started, in boredom, calculating values of what I have formalized as $f_n(a) = a^{f_{n-1}(a)}$ (also $f_0(a)=a$) for $a = 1.1$. He noticed that on his calculator it was not changing value ...
0
votes
2answers
49 views

Proving a summation

My exercise is to prove $\sum_{i=0}^n i = \frac{n(n+1)}{2} $. This is what I tried: Let $P(n) = \sum_{i=0}^n i$ Step 1: Show $P(1)$ is true $$P(1) = \sum_{i=0}^{1} i = 0 + 1 = 1$$ $$\frac{n(n + ...
1
vote
0answers
36 views

Divisible 4 for every different number?

My formula is for ABC 3 digits number; 100A + x*B + y*C. What should coefficient of B and C be for everytime different result for different number? (Result number ) mod 4 has to be zero. For ...
0
votes
1answer
50 views

Complexity of FFT Algorithm

OkayI am using iterative FFT algorithm and I have found that since there are 2N computation per stage and there are logN stages the complexity should be O(2NlogN) I can reduce the number of ...
2
votes
1answer
38 views

Recurrence relation of the following sequence?

This is the code: for (unsigned int i = 0; i < n; ++i) if (i % 2 == 0) ++k; And this is the output for when ...
2
votes
1answer
24 views

An inequality and random number and algorithm problem

I've been run into a problem which is absolutely not as simple as is looking, I just don't know how to describe it.I think it is a math problem eventually? Suppose a target number A and a mistake C ...
1
vote
2answers
77 views

How does this simplification work?

The following recursive function was given: $$T\left(n\right) = T\left(n - 1\right) + x$$ The author stated that by using repeated substitution we can solve the recurrence relation: The basic ...
3
votes
2answers
268 views

Algorithm for adding n 1-bit numbers

suppose adding two numbers, (that first number has a bits and second number has b bits) can be done in ...
0
votes
0answers
87 views

Local informatics Olympiad and Algorithm

I see one of recent local informatics Olympiad question. i have a trouble to solve it. any idea? hint? or solutions? thanks to all creative man. We have two function $P_1, P_2$ and input an array $n$ ...
2
votes
1answer
243 views

Turing machines that compute $\pi$

For each $K > 0$ there is a brut force Turing machine $\pi_K$ that "computes" the first $K$ digits of $\pi$ starting on the blank tape (all $b$s) with $K+1$ states $S \in \mathsf{S} = ...