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

learn more… | top users | synonyms

0
votes
0answers
28 views

Ackermann's Function

$A(m,n) = n+1$ if $m=0$$A(m,n) = A(m-1,1)$ if $n=0$$A(m,n)= A(m-1,A(m,n-1))$ This function blows off( I mean increases drastically) after a certain point. For example,$ A(2,4) = A(1,A(2,3)) = ...
0
votes
0answers
8 views

Finding the Primitive Recursive Function for the Rem Function

When trying to show the remainder function is a primitive recursive function as defined to be as below (Copied from Proof Wiki): $\operatorname{rem} \left({n, m}\right) = \begin{cases} 0 & : ...
0
votes
1answer
24 views

Solve the recurrence using the Master Theorem: $T(n) = 5T\left(\frac{n}{4}\right) + n\lg \lg n$

I am trying to solve the recurrence: $$ T(n) = 5T\left(\frac{n}{4}\right) + n\lg \lg n. $$ I tried to apply the Master Theorem but it didn't get me anywhere: $$ a=5,\; b=4\; \text{ and } f(n) = n\lg ...
0
votes
0answers
19 views

Solve the recurrence $T(n) = 2T(n/2) + n/\log n$

Hi am trying to solve the recurrence $T(n) = 2T(n/2) + n/\log n$. It almost matches the master theorem except for the $n/\log n$ part?
1
vote
0answers
20 views

Infinite series, continued fractions, nested radicals and such - is there a general recursive algorithm theory?

The nature of infinity and irrational numbers (among other things) always gave me trouble. But recently I learned to think about infinite sequences in terms of recursive algorithms and their time ...
0
votes
0answers
16 views

Recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$,$\sum\limits_{i=1}^{k}c_i < 1$ is linear

Let $L: \mathbb N_0 \to \mathbb N_0$ satisfy the recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$ with $c_i \geq 0$ for $i=0,\ldots, k$ and $\sum\limits_{i=1}^{k}c_i < ...
1
vote
1answer
47 views

How do you go about solving this recurrence?

How do you make an estimation for the substitution method, when the recursion tree did not help so much? I have a recurrence $$T(n) = 5\cdot T(n/3) + n (\log n)^2$$ And upon doing the recurrence ...
0
votes
0answers
46 views

Specify an O(logn) algorithm which either finds an i, where i is an element of {1,2,…n} such that S[

Let S be an array of n integers such that S[1] < S[2] <...< S[n] Specify an O(logn) algorithm which either finds an i, where i is an element of {1,2,...n} such that S[ i ] = i or else ...
1
vote
1answer
62 views

Is the definition of recursive function unchanged if we restrict substitution to binary composition?

When defining recursive functions, are the following two statements equivalent?$$f:\mathbb{N}^n\rightarrow\mathbb{N}^m, g:\mathbb{N}^m\rightarrow\mathbb{N}^k \text{ recursive}\implies g\circ f \text{ ...
0
votes
0answers
29 views

Time complexity of $T(n) = 2^n + 2\sum_{i=1}^{n-2} T(i)$

$$ T(n) = 2^n + 2\sum_{i=1}^{n-2} T(i)$$ $$ T(0) = 1 , T(1) = 2 $$ This is my $T(n)$, and I need to find its time complexity. I know the answer is $T(n) = \theta (n2^n)$, but I have a problem with ...
1
vote
0answers
89 views

Finding a solution to $\sum _{n=1}^{n=k} \frac{1}{n^x}+\sum _{n=1}^{n=k} \frac{1}{n^y}=0$

Scroll down to the update to see what I am meaning. The Mathematica program below finds a solution to the equation: $$\sum _{n=1}^5 \frac{1}{n^x}+\sum _{n=1}^5 \frac{1}{n^y}=0$$ My question is if you ...
0
votes
0answers
112 views

Counterexample for Algorithm of Isomorphism testing of Non-Symmetric Matrices

Claim: $E, F$ are non-symmetric 0-1 matrices of dimension $m \times n$ where $m>n$. Given $F \neq E$, it takes maximum maximum $O( \frac {m^{log_2(m)}} { 2^{\sum log_2(m)} })$ times to check ...
1
vote
1answer
27 views

Algorithm for equality of trees of restricted depth

Are there any efficient algorithms to decide whether two trees of limited depth, where all nodes have a finite number of childs, are equal interpreted as finite sets with the leaves the "atomic" ...
3
votes
2answers
128 views

Give an upper bound for a function satisfying $f(n)=4f(n−1)+n$ [closed]

A function $f(n)$ satisfies the recurrence $f(n)= 4f(n−1)+n$ for real numbers. Give an upper bound for $f(n)$. Is the attached picture the correct answer?
1
vote
0answers
45 views

Number of Hamilton paths in an extremely dense undirected simple graph

What is the fastest way (algorithm) to calculate the number of Hamilton paths in an extremely dense undirected simple graph (approximately 99.99% edges are connected)? I was thinking of the following ...
4
votes
2answers
65 views

Mathematically, how does one find the value of the Ackermann function in terms of n for a given m?

Looking at the Wikipedia page, there's the table of values for small function inputs. I understand how the values are calculated by looking at the table, and how it's easy to see that 5,13,29,61,125 ...
2
votes
1answer
37 views

I want an upper bound for a real function f(x,y,z) - prime counting

The function $f:\mathbb R^3\to\mathbb R$ is: $$\displaystyle f(x,y,z)=\frac{x}{yz}-\frac{\lfloor x/y\rfloor}{z} , \; \text{where}\,\; x,y,z>1.$$ If there is an upper bound less than 1, then it is ...
1
vote
0answers
26 views

When the integers got upset.

I have been stuck with this problem for quite large time. https://www.hackerearth.com/code-monk-bit-manipulation/algorithm/when-the-integers-got-upset/. In short what is says is: There are two arrays ...
0
votes
2answers
34 views

Finding Recursive Definition for the following:

How would i start off to find a recursive definition for $X_{0}$=.19 $X_{1}$=.1919 $X_{2}$=.191919 ... $X_{n+1}$= what goes here?
3
votes
4answers
75 views

Recurrence relation $T(n+1)=T(n)+⌊\sqrt{n+1}⌋$?

Consider the following recurrence relation $T(1)=1$ $T(n+1)=T(n)+⌊\sqrt{n+1}⌋$ for all $n≥1$ The value of $T(m^2)$ for $m≥1$ is $(m/6) (21m – 39) + 4$ $(m/6) (4m^2 – 3m + 5)$ $(m/2) (m^{2.5} – ...
0
votes
2answers
119 views

Write recurrence relation for above algorithm and solve it using Iteration Method.

Consider the following recursive algorithm for computing the sum of the first $n$ squares: $\sum \limits _{i=1} ^n i^2 = 1^2 + 2^2 + \cdots + n^2$. Algorithm: ...
0
votes
2answers
322 views

Write an algorithm to find minimum number from a given array of size ‘n’ using divide and conquer approach.

In Divide and conquer strategy, three main steps are performed: Divide: Divides the problem into a small number of pieces Conquer: Solves each piece by applying divide and conquer to it ...
0
votes
2answers
36 views

Solving recurrence using recurrence trees.

I have a recurrence which I know has the solution $O(\lg n)$, it looks like this: $$T(n) = T(\sqrt n) + \lg n$$ If I understand correctly, the recurrence tree method involves looking for the term ...
-1
votes
1answer
67 views

Lower bound for two eggs problem

I have just read about two eggs problem. I know that with decreasing amount of jumps we can reach worst case scenario of first jump $a = \sqrt{2n}$, $n$ is the number of floors, how about the lower ...
1
vote
1answer
20 views

Using rsolve in Maple

I have tried using rsolve in Maple to obtain a recursion formula from an ordinary differential equation with summations. I get Is there some reason for Maple ...
-1
votes
1answer
43 views

Time Complexity

Prepping for an exam and wondering whether I correctly calculated the time complexity. Function is given as: $function XYZ(n:integer)\\ begin for\ i:=1 \ do \ 2*n^2 \ do;\\ ...
0
votes
1answer
23 views

Factorial Series Written As Recursive Definition

I have a factorial series as shown below: \begin{equation} (2n+1)!~\text{for all $n \geq 0$} \end{equation} And I would like to know if the recursive definition that I wrote is accurate: ...
1
vote
1answer
22 views

Recursive Definition of a Series

I have a series such as the one below: \begin{equation} 2^n(\sum\limits_{i=2}^{n+1}i)\text{ for all $n \geq 1$} \end{equation} I need to write a recursive definition for it. Here's what I have so ...
1
vote
2answers
26 views

Summation of differences in exponent

Came to this summation during an algorithm analysis problem and any help would be much appreciated:$$\sum_{j=1}^n3^{n-j}$$
1
vote
1answer
28 views

How to give a recursive definition and a direct formula and prove that they both are equivalent.

How to give a recursive definition and a direct formula and prove that they both are equivalent. for example, 10,13,16,19,22,25 I know the formula for this is a,a+d,a+2d,a+3d,... ...
0
votes
1answer
29 views

given $n$ stairs, how many number of ways can you climb either step up one stair or hop up two?

this is the question given $n$ stairs, how many number of ways can you climb either step up one stair or hop up two? I need to include the number of ways for $n=1$ through $6$ as well. My ...
2
votes
0answers
19 views

Help solving the recurrence $W(n)=W(n/5)+W(7n/10)+\Theta(n)$.

Let $W(n)=W(n/5)+W(7n/10)+\Theta(n)$ for $n>5$ and $W(n)=\Theta(1)$ for $n\leq 5$. I want to show that $W(n)\in \Theta(n)$. Attempt 1 I understand the technique used in this question that solves ...
1
vote
0answers
15 views

nodes equation cant find formula.

Given the level $N$ at which a node $X$ is located in a binary tree, to search for node $X$ according to level-order traversal, we can use the knowledge of level N where $X$ is located to narrow our ...
0
votes
0answers
17 views

Finding the smallest decision tree of a Boolean function

From Computational Complexity: A Moden Approach, A decision tree is a model of computation used to study the number of bits of an input that need to be examined in order to compute some ...
3
votes
1answer
38 views

A recursive definition

I have this problem: Q4 of this Prove by induction that no matter how the dots are coloured red and blue, it is possible to have a successful trip around the circle if you start at the correct ...
1
vote
1answer
58 views

Recurrence relation using substitution method

How do I solve the following recurrence using substitution method? $$T(n) = T(n-1)+C$$ I've found reference to so many examples on line but most of the examples are of the form $$T(n) = ...
0
votes
0answers
22 views

Recursive formula for an integral involving multiple inner products

Motivation: I am trying to form a Bayesian model where I will be performing frequent state-updates. I am seeking to find a recursive formula for a certain quantity that will enable me to perform this ...
0
votes
0answers
17 views

Solve a three term recursion

Consider the recursive function: $$f(a,b,c) = \frac{a}{t}(1-f(b,a-1,c)) + \frac{b}{t}f(a,b-1,c) + \frac{c}{t} f(a+1,b,c-2)$$ where $$t = a + b+c\\f(a,0,0) = 1$$ This arises in the context of game ...
0
votes
0answers
70 views

Chudnovsky binary splitting and factoring

In this article, a fast recursive formulation of the Chudnovsky pi formula using binary splitting is given. For $S(a,b)$: $$ m = (a + b) / 2 $$ $$P(a,b) = P(a,m) P(m,b)$$ $$Q(a,b) = Q(a,m) Q(m,b)$$ ...
0
votes
2answers
31 views

Tree. Number of nodes and children

Suppose a given tree $T$ has $n_1$ nodes that have $1$ child, $n_2$ nodes that have $2$ children, . . . , $n_m$ nodes that have $m$ children and no node has more than $m$ children, how many nodes have ...
0
votes
1answer
38 views

Identify a repeating pattern within large number set

I haven't studied maths for over 30 years, but have been asked to solve a problem. We have a very large data set, each data point contains 11 numbers. We would like to identify a recurring pattern ...
0
votes
0answers
27 views

Master theorem with n! and constant function

I'm learning master theorem from this Youtube video. It's very easy to understand. However, it doesn't explain how to tackle n! function. How do I solve it? For example - T(n) = 16T($\frac{n}{4}$) ...
1
vote
0answers
20 views

Average gap of a sorted sequence.

Considering a sorted sequence $a_0\leq a_1\leq...\leq a_{n-1}$ and defining the average gap of any subsequence to be:- $f(i,j)=\frac{(aj-ai)}{(j-i)}$, I would like to show that for all $ ...
0
votes
0answers
29 views

Deriving explicit formula from recursive function

I have a recursive function R that is defined as follows: R(0) = 1 R(1) = 1 R(2) = 2 R(2n) = R(n) + R(n + 1) + n (for n > 1) R(2n + 1) = R(n - 1) + R(n) + 1 (for n >= 1) Is it possible to define a ...
0
votes
0answers
8 views

Algorithm(code) problem about division

I am stuck with the last part of my algorithm. I am using a Prolog program. language to solve this problem. I have to write program to solve a typical divison task with quotient and reminder. Here ...
0
votes
0answers
64 views

Prove the number comparisons it takes to find the min and max of a list by the split and conquer method

Prove that the number of comparisons it takes to find the min AND max of a list by the split and conquer method (split a list in half until there are multiple subsets of just 2 elements and compare ...
0
votes
0answers
48 views

Recursive Newton-Type Algorithm

First of all, I'm new to this forum and I'd like to introduce myself. My name is Julio, I'm industrial engineering and at this moment I'm doing some research about estimation of power components and ...
1
vote
1answer
65 views

Use a divide and conquer algorithm to find f(n)

Use $f(1) = a$ and $f(n) = 3f(n/2) + bn$ to show that $f(n)= a(3^m) + 2(b)(3^m) - b(2^{m+1})$. Also note that $n=2^m$ Using the recurrence relation: $f(n)= a^m (f(1)) + \sum_{i=1}^{m} ...
0
votes
0answers
39 views

How to solve three recurrences dependent on each other?

Given $a$,$b$,$s$ and $y$. Let $U_0=s$, $V_0=0$ and $W_0=s$, and $U_{n+1}={s b ((1-2 y) V_{n}+2 y W_{n})}/\sqrt{(1-y) (U_{n}^2 a^2+V_{n}^2 b^2)+y W_{n}^2 b^2}$ $V_{n+1}=-s a U_{n} ...
0
votes
0answers
16 views

Binary search for the worst case.

I want to analyze binary search for the worst case, completely mathematically without any ellipses(...). I solved out the recurrence of the binary search. $$ T(n+1)=T(n/2)+C $$ I've already searched ...