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

learn more… | top users | synonyms

2
votes
1answer
41 views

Limit maze to region

I have created a random hexagonal maze using an algorithm. But how do I limit the maze to just the green hexagonal region in the following picture? Note that the size of the maze and the green region ...
2
votes
0answers
43 views

Recurrence relationship of Hamiltonian backtracking

I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors. After finding ...
2
votes
2answers
72 views

Find the gcd of two polynomials: $f(x) = x^4+1$ and $g(x)=x^2-1$ using the Euclidian algorithm.

I need to find the gcd of two polynomials: $f(x) = x^4+1$ and $g(x)=x^2-1$ using the Euclidian algorithm. Wolfram shows that the gcd is equal to $1$, but for some reason I don't get the same answer. ...
2
votes
1answer
56 views

Hexagon “maze” algorithm

Can anyone suggest a good algorithm to create structures like this? Note that what I what I am asking for is not a true maze with one start and one solution. Rather, it's for a video game, so like ...
1
vote
1answer
38 views

Probability to iteratively and independently remove $n$ elements until all gone

The problem is as follows: Let S be a set of n elements. At the first stage each element in S is in- dependently removed with probability p. Those elements not removed constitute the set S1. ...
0
votes
2answers
62 views

recurrence formula for number of decimal numbers with some restrictions

I ran into a Olympiad Question that so difficult, if $a_n$ be the number of decimal numbers with length $n$ that has no $0$ in the digits and also has not any combinations $11,12,21$, I want to find ...
0
votes
0answers
50 views

Finding Explicit Function from a reclusive formula

I have been working on a project that will move much faster if I can write a recursive formula as an explicit formula. Let, $f(m-1,i)=i*f(m,i)-f(m,i+1)$ $i \in \mathbb{N}$ Thus, ...
0
votes
0answers
12 views

What to do when RHS of inhomgenous equation is to the nth power?

This is from an algorithm analysis course. I'm trying to analyse the time complexity of a recurrence relation. I have a inhomogneous equation for which I need to derive the characteristic equation. ...
0
votes
1answer
41 views

How to solve this recurrence, $T(n) = T(\sqrt{n}) + n$ using recursive tree method?

How to solve this recurrence, $ T(n) = T(\sqrt{n}) + n $ using recursive tree method? I draw the tree and got a sum, $ T(n) = T(1) + ( n + n^{\frac 12} +n^{\frac 14}+n^{\frac 18}+\ldots +1) $ I need ...
0
votes
0answers
46 views

Can linear execution time be achieved [duplicate]

The SELECT algorithm determines the $i$th smallest of an input array of $n>1$ distinct elements by executing the following steps. Divide the $n$ elements of the input array into $\lfloor ...
3
votes
1answer
50 views

How to find an explicit formula for a recursive function?

Define $$ S_{n+1} = \frac{S_n^2+x}{2S_n}$$ and $S_1 = k$, where x,k > 0. find an explicit formula for $S_n$ in terms of n. I don't even know where to begin. I tried using algebraic ...
2
votes
1answer
97 views

Why does Archimedes Method to calculate Pi decrease in precision after a certain time?

i`m using the following recursive formula to calculate Pi based on Archimedes ideas. $$ S' = \sqrt{2-\sqrt{4-S^2}} $$ The formula gives back the edge length of a Polygon B based on the edge length of ...
2
votes
1answer
57 views

Understanding the Power Iterative Method to find eigenvalues

I'm slightly confused about how to use the power method and the steps to calculate an eigenvalue. - I understand that the power method is defined as U(x+1) = AU(x)/a(x) where "a" is the first ...
0
votes
1answer
39 views

Iterative Logarithm in Recurrence Relation?

Anyone Could describe me How we can solve this recurrence relation? $T(n) = T(\log n) + O(1)$ $T(1) = 1$ a) $O(\log n)$ b) $ O (\log^* n) $ c) $ O (\log^2 n) $ d) $ O (n / \log n) $ Our TA ...
2
votes
1answer
133 views

Relax function on Bellman Ford Algorithms

In a Weighted Directed Graph $G$ (with positive weights), with $n$ vertex and $m$ edges, we want to calculate the shortest path from vertex $1$ to other vertexes. we use $1$-dimensional array $D = ...
3
votes
2answers
61 views

n bag of sand and one algorithms

We have $n$ bags of sand, with volume $$v_1,...,v_n, \forall i: \space 0 < v_i < 1$$ but not essentially sorted. we want to place all bag to boxes with volumes 1. We propose one algorithm: ...
0
votes
3answers
53 views

Order of Natural Numbers in Algorithms

Could anyone describe, why this is a True statements? if $f_i$ be a function of natural numbers to natural numbers and $f_i(n)=O(n)$ then $\Sigma_{i=1}^{n} f_i(n)=O(n^2) $
0
votes
1answer
24 views

Why $T(n) = 2t(n/2) + \log n$ is in $ O(n)$?

My professor said that $T(n) = 2t(n/2) + \log n$ is in $O(n)$ I checked with Master Theorem and I did not really understood why. By Case1 (which would give us exactly $O(n)$) we have $a = 2, b = 2, ...
3
votes
2answers
99 views

$ T(n)= T(\log n)+ \mathcal O(1) $ Recurrence Relation

what is the solution of following recurrence relation? $$\begin{align} T(1) &= 1\\ T(n) &= T(\log n) + \mathcal O(1) \end{align}$$ a) $O(log n)$ b) $ O (log^* n) $ c) $ O (log^2 n) $ d) $ ...
0
votes
1answer
63 views

How to prove a recurrence with multiple terms?

I have to prove that the recursion: $$T(n) = T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + n $$ is $$ T(n) = Θ(n*\log n)$$ As you can see, the reccurence has two different terms that ...
0
votes
1answer
23 views

Computation Operation in one Recurrence Relation

We want to calculate $T(n)$ from recurrence relation $ T(n)= \Sigma_{i=1}^{n-1} T(i) \times T(i-1)$` and we know $T(0)=T(1)=2$. How many computation operation, an Efficient Algorithm needs for ...
0
votes
0answers
40 views

recursive-algorithm problem

I am not to sure were to begin Thanks
0
votes
0answers
51 views

Best strategy for this archery-based probability game

This is with reference to the comments posted by @Trenin on my answer to this question. He says that since 2 players strategies depend on each other, we can't get the best strategy so easily. My ...
0
votes
1answer
92 views

Fan speed algorithm

I'm a programmer an I think my problem related to mathematics! I want when CPU have a static percentage of load (for example $10\%$) fan also have static rpm (Rotations per minute). But for now I have ...
0
votes
1answer
28 views

Recursive function with p=2/3 to call itself and 1/3 to return always ends?

So I was reading Godel, Escher, Bach and this problem came up: Let f(t) { 1)Generate random number k 2) if( k mod 3 = 0 or k mod 3 = 1 ) call f(t) //so 2/3's of the time, a new recursion level ...
0
votes
1answer
67 views

When drawing a recursion tree, how does b effect the tree if it is given?

So the problem I have is T(n) = T(n/8) + T(7n/8) +5n. I need to draw a recursion tree to prove that T(n) = Ө (n log 8 n ). I also need to show that T(n) = O (n log 8 n ) and T(n) = Ω (n log 8 n ). ...
3
votes
2answers
54 views

Fibonacci recursive algorithm yields interesting result

After writing a program in Java to generate Fibonacci numbers using a recursive algorithm, I noticed the time increase in each iteration is approximately $\Phi$ times greater than the previous. ...
2
votes
1answer
56 views

Recursive Alegbraic Equation for binary trees? [duplicate]

Consider the number $b_h$ of binary trees of height $h$, where height is being measured by the number of levels. An empty tree has height $0$, a single node binary tree has height $1$, and there ...
0
votes
0answers
34 views

Help Solve Recurrence Relation$ T(n) = T(n-1) + O(n)$

This is how far I have gotten: $$T(n) = T(n-1) + O(1)$$ $$T(n-2) = T(T(n-2)) + O(1)) + O(1)$$ $$T(n-2) = T(n-2) + O(2)$$ $$T(n-3) = T(T(n-3) + O(1)) + O(2)$$ $$T(n-3) = T(n-3) + O(3)$$ Finally ...
1
vote
1answer
96 views

Help Solve Recurrence Relation T(n) = 3T(n/2) + O(n)

Given recurrence $$T(n) = 3T(n/2) + O(n)$$ $$let\:cn >= O(n)$$ for some constant c I can bound $$T(n)$$ in terms of $$T(n/2)$$ so I have $$T(n) <= 3T(n/2)+cn, \ \ \ \ \ k = 1 \ call$$ So I ...
0
votes
1answer
40 views

Need to understand the end of Karatsuba algorithm running time proof

I cannot understand the end of Karatsuba algorithms running time proof. Initially we have formula $$T(n) = 3T(\frac{n}{2}) + rn$$ if n > 1 $$T(n) = r $$ if n = 1 , where r is a constant. We assumed ...
3
votes
1answer
51 views

How to prove that calculating Ackermman function stops?

Let $$\begin{eqnarray*} A(0,y) &=& y+1 \\ A(x+1,0) &=& A(x,1) \\ A(x+1,y+1) &=& A(x,A(x+1,y)) \end{eqnarray*}$$ be Ackermann function. How to prove by structural induction ...
0
votes
0answers
63 views

$T(n) = T(n/3) + T(2n/3) + cn$ - recursion tree with constance $c$

I have a task: Explain that by using recursion tree that solution for: $T(n)=T(\frac n3)+T(\frac 2n3)+cn$ Where c is constance, is $\Omega(n\lg n)$ My solution: 1. Recursion tree for $T(n)=T(\frac ...
1
vote
0answers
87 views

Recursion tree T(n) = T(n/3) + T(2n/3) + cn

I have a task: Explain that by using recursion tree that solution for: $T(n)=T(\frac n3)+T(\frac 2n3)+cn$ Where c is constance, is $\Omega(n\lg n)$ My solution: 1. Recursion tree for $T(n)=T(\frac ...
1
vote
0answers
24 views

algorithm related to dyadic decomposition

Starting from an integer $n >0$, iterate the two operations of substracting one and dividing by $2$ (when the number is even) until $1$ is reached. Thus when the number is odd we can only substract ...
1
vote
0answers
37 views

Using FFT to compute DFT of a polynomial

i currently studying about FFT and DFT and we were given simple question: Use the recursive FFT to compute the DFT of this polynomial of '3' degree: $$-1\:+\:4x\:+\:3x^2$$. So, i go to this ...
0
votes
1answer
31 views

Can someone check my answers to this problem?

This is from Discrete Mathematics and its Applications Definition of recurrence relation from book From my understanding, compounded annually means that every year(annually) the account will ...
0
votes
0answers
39 views

Blum Micali Algorithm Security By Seed Size

I'm coming from a computer science background, so I'm having some difficulty with these high level mathematics. With reference to the Blum Micali algorithm: (underscore represent subscript) ...
0
votes
1answer
24 views

Feasible method of grouping relations

This might be a bad question, I hope not so bad. Problem is I have a set of relations(millions), presumably two arrays hold two nodes(starting, and ending), which together forms a relation(edge). I ...
3
votes
0answers
72 views

Algorithm for Converting Rational Into Surreal Number

I'm writing a library in Haskell that represents the class of surreal numbers, which like many things can be read about here. I've run into a problem in converting between other classes of numbers ...
3
votes
0answers
102 views

How can I convert a recursive equation to a non-recursion one? [duplicate]

While I am aware of several other similar question which have been asked in the past, my mathematical education only extends through calculus, making them beyond my comprehension, and I believe this ...
5
votes
2answers
353 views

Characteristic equation. What is it?

Consider a recursive equation: $$ a_n = A a_ {n-1} + Ba_ {n-2} $$ And for this type of equation, there is characteristic equation: $ x ^ 2 = Ax + B $. What does exactly means that this equation is ...
1
vote
0answers
26 views

Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than 2 I should choose a special partitioning hyperplane for the divide and conquer algorithm to get O(n log n). I am confused because to choose this ...
1
vote
1answer
150 views

Give tight asymptotic bounds for the following recurrence. T(n) = 3T(n/3)+log n

Give tight asymptotic bounds for the following recurrence. Justify your answers by working out the details or by appealing to a case of the master theorem $$T(n) = 3T\left(\frac n3\right)+\log(n)$$ ...
3
votes
1answer
40 views

Finding all local $k$-maximums in sequence $a_1, a_2, \ldots a_n$.

For given sequence of numbers $a_1, a_2, \ldots, a_n$ we say that $a_i$ is $k$-local maximum, if $i > k$ and $a_i$ is largest of numbers $a_{i - k}, a_{i-k+1}, \ldots, a_i$. How can we find all ...
3
votes
1answer
53 views

Finding $m$ largest numbers from union of $k$ sorted lists $A_1, A_2, \ldots, A_k$

We are given $k$ sorted lists $A_1, A_2, \ldots A_k$ with corresponding sizes $n_1, n_2, \ldots n_k$. How can one find $m$ largest elements (numbers) from union of lists $A_1, A_2, \ldots, A_k$? We ...
2
votes
0answers
96 views

How can we find the elements?

I want to describe an algorithm with time complexity $O(m)$ that, given a set $M$ with $m$ numbers and a positive integer $p \leq m$, returns the $p$ closest numbers to the median element of the set ...
3
votes
1answer
41 views

Question about recursive algorithm

I have following problem: $$f(n)=\frac{1}{1^2+1}+\frac{2}{2^2+1}+\frac{3}{3^2+1}+\cdots+\frac{n}{n^2+1}$$ Write recursive algorithm for $f(n)$ Prove that recursive algorithm is correct ...
3
votes
1answer
91 views

How can I recursively approximate a moving average and standard deviation?

Consider a sequence of measurements $(x_1, x_2, ...)$. Let $\mu_n$ be the $p$-period moving average defined by $$\mu_n = \frac{1}{p}\sum_{i=n-p+1}^nx_i$$ and $\sigma_n$ be the $p$-period moving ...
1
vote
2answers
164 views

Dynamic programming:Making a Change

I'm practicing problems on dynamic programming.The problem is as follows: You are given n types of coin denominations of values v(1) < v(2) < ... < v(n) (all integers). Assume v(1) = 1, so ...