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

learn more… | top users | synonyms

1
vote
1answer
115 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
21 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
89 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
47 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
22 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
50 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
47 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
0answers
20 views

Developing closed-form from recursive definition

Here is a recursively-defined function where c, d ∈ N. T(n) =    c, if n = 0 d, if n = 1 2T(n − 1) − T(n − 2) + 1, if n > 1 Carry out the five steps for repeated substitution to prove a ...
0
votes
1answer
69 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
84 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
60 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
0answers
13 views

Integer multiplication in 5T(n/3) [duplicate]

x and y has n bits x=x0*(10^2n/3)+x1*10^n/3+x2 y=y0*(10^2n/3)+y1*10^n/3+y2 x*y=x2y2+(x2y1+x1y2)10^n/3+(x2y0+x1y1+x0y2)10^2n/3+(x1y0+x0y1)10^n+x0y0*10^4n/3 now 9 multiplication of n/3 bit numbers ...
0
votes
1answer
25 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
100 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
31 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
65 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
86 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
26 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
64 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
175 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
45 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
248 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
25 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
30 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
63 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
64 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
38 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
34 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?
4
votes
0answers
109 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
36 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
39 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 ...
-1
votes
1answer
394 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
58 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
30 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. ...
0
votes
1answer
47 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
29 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
46 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
35 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
35 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
33 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
75 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
200 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 ...
2
votes
0answers
74 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
188 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} = ...
1
vote
1answer
45 views

Number of strings of size $k$ that do not have 'ab'

Consider $\Sigma = \{a,b,c\}$ and the language $L$, the set of all strings that do not contain 'ab' Find strings, of size $k$ is in $L$ ($L_k$) Consider $A_k$ (strings of size $k$ that end in $a$) ...