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

learn more… | top users | synonyms

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
40 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
501 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
74 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
49 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
31 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
48 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
38 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
76 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
205 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
80 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
200 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$) ...
1
vote
1answer
84 views

Hashing With Chaining Collision

We have $1000$ elements with key=1 to 1000, and a hashing function $$ h(i)=i^3 \mbox{ mod } 10 $$ for an array with length $10$ (array index from $0$ to $9$) with chaining method. What is the ...
0
votes
1answer
120 views

Water Box with n Liter

I ran into a basic challenging problem. I see an high school local math Olympiad question. we have a box that keep n Liter water. each time we extract 1/k Water from box. how many times (minimum) we ...
0
votes
1answer
87 views

Polynomial Multiplication through Toom-Cook into Karatsubas

I'm trying to solve a polynomial multiplication problem recursively through using Toom-Cook (Toom-3) once and Karatsuba (Toom-2) five times, although I'm stuck after the first round of Karatsubas. ...
1
vote
1answer
37 views

Need an Algorithm Such that $\sum_{k-i}^{j}{A[k]}$

I need an algorithm for real application. Suppose we have array A (positive & negative ) numbers. we want to find index i, j such that $\sum_{k-i}^{j}{A[k]}$ has the lowest difference to zero. ...
0
votes
0answers
44 views

Can we sort 6 numbers with at most 9 comparison? [duplicate]

i know there is an algorithm to sort 5 numbers with 7 comparison. Can we sort 6 numbers with at most 9 comparison? thanks to all.
2
votes
3answers
115 views

2000 Olympiad in Informatics Question on Box

I have an old Olympiad question on informatics. There are 31 boxes. In each box there is one number. We know the number if and only if we open the box. We want to calculate the minimum number of ...
1
vote
1answer
61 views

Problematic Initial Condition of a Recurrence Relation

I encountered this equation, and tried to solve it: $T(n) = T(\sqrt{n})+log(n)$ Under the initial condition T(1)=1. Can someone tell me why is this initial condition helpful? I mean, of course ...
0
votes
2answers
125 views

Meaning of 'expected value' in the following problem

Ok, I have found an interesting probabilites problem on TopCoder. I have truncated the statement: "What is the expected number of dice throws needed to attain a value of at least n (candies, in this ...
0
votes
1answer
181 views

Recursive definition of the set of odd numbers

Show that the following is another recursive definition of the set ODD (keep in mind you’ll need say something about even numbers too): Rule 1: 1 and 3 are in ODD. Rule 2: If x is in ODD, then so is x ...
0
votes
1answer
121 views

Recurrence relation from code

My Friends, Hi, I see an old book in mathematics for computer science. everyone could help me, for example how we calculate the order (Time complexity) of following code: ...
-1
votes
2answers
217 views

Solving a recurrence relation with square root

I ran into a bad recurrence relation. Anyone would calculate T(n) or add some hint? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 }\\ \sqrt{1/2[T^2(n-1)+T^2(n-2)]+}n ,\quad ...
0
votes
1answer
86 views

Height of Recursion Tree for $T(n, k) = T(n/2, k) + T(n, k/4) + kn$

If we use a recursion tree for solving $$\begin{cases} T(*,1)=T(1,*)=a \\ T(n,k)=T(n/2,k)+T(n,k/4)+kn \end{cases}$$ What is the height of the recursion tree? Any idea or solution highly ...
0
votes
1answer
175 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
-1
votes
1answer
106 views

Solving the recurrence relation $T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n$

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated. My solution is: $n=3^m \to ...
2
votes
1answer
633 views

Recurrence Relation - Merge Sort

We know the recurrence relation for normal merge sort. It is T(n) = 2T(n/2) + n. After solving it we can get T(n) = cnlogn. I ...
1
vote
2answers
57 views

Solve $T(n) = T(n-1)+\log^2(n)$

I was trying to solve $T(n) = T(n-1)+\log^2(n)$ using substitution method and variables substitution but I can't find the correct answer. My attempt: Let $m = \log(n)$ then $T(2^m) = ...
0
votes
1answer
49 views

Turn recursive definition of a function into its close form

I'm creating a tree diagram, and I'm trying to calculate the amount of white spaces I need at the left side. As you can already see this is done in a program. The formula goes like this: $$ ...
3
votes
5answers
127 views

How to solve the recurrence relation $T(n) = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2$

I'm trying to solve a recurrence relation for the exact function (I need the exact number of comparisons for some algorithm). This is what i need to solve: $$\begin{aligned} T(1) &= 0 \\ T(2) ...
2
votes
1answer
87 views

Recurrence - using power series

Could you help me in solving this recursion( a closed form ) using power series $\mu(n)=\mu(n−1)k_0+(n−1)\mu(n−2) k_1 \tag 1$, where $k_0,k_1$ are constants $\mu(0)=3,\mu(1)=5$ HINT: We can think ...
0
votes
1answer
28 views

Summation of infinte series

Sir, I have three infinite summation $A =J_1 \sum_{n=2}^\infty (n-1) f(n-2) \tag 1$ , $B =\sum_{n=0}^\infty f(n) \tag 2$ and $C =J_2\sum_{n=1}^\infty f(n-1) \tag 3$, with ...
1
vote
1answer
56 views

Infinite series for recurrence

Question 1 If I define $A(z) = \sum_{n \ge 0} a_n \frac{z^n}{n!} \tag 1$ (where $a_n$ are $3\times 3$ constant matrices indexed with n), then can we re-write $\sum_{n \ge 1} a_{n-1} \frac{z^n}{n!} ...
3
votes
2answers
101 views

Fibonaaci Recurrence

This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities Given Data in question ...
0
votes
0answers
29 views

Solving a simple Recurrence in summation form(very special case)

I have a bit confusing recursion form $\sum_{n=2}^{\infty}\{f(n)\frac{n}{n-1}\}=C, \tag 1$ $f(0)=b,f(1)= a,f(2)=c$ and $C$ are constants. Could you help me to solve this recursion or help me to ...
1
vote
0answers
53 views

Solving the recursion $F(n)=K_0F(n-1)/(n-1)+K_1F(n-2)/(n-2)$

Please help me in solving the recursion $F(n)=K_0\frac{F(n-1)}{n-1}+K_1\frac{F(n-2)}{n-2}$, preferably using power series for the values of $F(n)$ in terms of $n$. Here $K_1$ and $K_2$ are ...
6
votes
3answers
385 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
7
votes
3answers
328 views

Solving recurrence relation: Product form

Please help in finding the solution of this recursion. $$f(n)=\frac{f(n-1) \cdot f(n-2)}{n},$$ where $ f(1)=1$ and $f(2)=2$.
2
votes
1answer
41 views

Primitive-recursive functions and polynomial equations

I am looking for examples of primitive-recursive functions $f:\mathbb{N}\rightarrow\mathbb{N}$ that can not be written as a pair of polynomials, i.e. $$f(n) = m \Leftrightarrow P(n,m) = Q(n,m)$$ ...
0
votes
0answers
27 views

Comparing Generalized Continued Fractions

Gosper lays out a method (under Approximations) for comparing regular (a.k.a simple) continued fractions which have all partial numerators set to 1. Continue comparing terms until they differ, then ...
3
votes
1answer
226 views

How to solve this recurrence Relation - Varying Coefficient

Sir,I have two questions related to this recurrence relation. It has been messing with me for long. Because of this I couldn't proceed my work for some time .This contains a polynomial term n+2 in ...
0
votes
0answers
27 views

Question about set and series notation in the GSP Algorithm

I tried this in programming forums with no luck and since my primary issue is with the notation, I'm asking here: I have the definition of the GSP Algorithm: Definition However I don't understand ...
0
votes
0answers
31 views

Produce a list of the most-similar units, given various correlations/relationships

I have a database full of units (U1 - U50, U51...) where every unit has the same standard attributes (A1 - A10) and where a % of each attribute defines the amount of that attribute for that particular ...