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

learn more… | top users | synonyms

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
28 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
35 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
79 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
132 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
433 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
38 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
72 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
21 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
48 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
24 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
27 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
37 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
24 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
24 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
39 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
66 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
23 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
86 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
63 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
46 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
30 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
31 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
9 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
71 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
51 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
69 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
41 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
19 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 ...
0
votes
2answers
64 views

Asymptotic bounds for $T(n)=T(n-2)+n$

I am trying to figure out how to find the Asymptotic bounds for $T(n)=T(n-2)+n$ and I am pretty sure that I need to use the substitution method. I have what I believe is a proof using the Subtract ...
1
vote
1answer
55 views

Prove by induction T(n) = T(⌊n/2⌋) +T(⌊7n/16⌋) + n

Prove by induction on n that T(n)=O(n), where T(0)=1, T(n) = T(⌊n/2⌋) +T(⌊7n/16⌋) + n So far I have, Base Case: n = 1 [1/2] + [7/16] + 1 T(1) = 1 Induction hypothesis: Assume that for arbitrary ...
3
votes
3answers
172 views

if I know $f(x+1) = 2f(x) + 1$, how do I solve f(x)

This is just my thought on run time of a binary search: if you are allowed to make 1 comparison, you can search a sorted list of length 1, but if you are allowed to perform 2 comparisons, you can ...
1
vote
0answers
45 views

Generalization of a FFT with powers of 3

I'm not satisfied with the current answers asked about this on MathSE. So I'm going to ask: Describe the generalization of the FFT algorithm to the case in which n is a power of 3. What's the ...
0
votes
1answer
35 views

Analysis of Recursive Algorithms

So say I'm going to analyze a factorial function: pseudocode: F(n) if n=0 return 1 else return f(n-1)*n This is my basic operation: $F\left(n\:-\:1\right)\cdot n$ now when it comes to the ...
0
votes
0answers
94 views

Help unrolling a recursive function

I want to calculate a recursive function $$f : \Bbb{Z} \times \Bbb{Z} \rightarrow \Bbb{Z}$$ $$f(n, m) = f(n,m-1) + f(\lfloor n/m \rfloor,\lfloor n/m \rfloor - 1) + \textrm{other non-recursive stuff}$$ ...
1
vote
2answers
57 views

Recursive algorithms for string operations

I am trying to write recursive algorithms for the following string operations: 1) An algorithm to reverse a string. 2) An algorithm to test if two strings are equal to each other. 3) An algorithm ...
0
votes
0answers
32 views

Problem involving joining up three sided shapes

You are given a collection of three sided shapes. They each have certain type of texture. 0 being rough and 1 being smooth. ...
1
vote
1answer
53 views

Asymptotic equalities in master theorem proof

In all proofs of master theorem I've found so far (Cormen et al., also here http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec19-master/mm-proof.pdf), there is essentially a following series ...
2
votes
1answer
109 views

Minimally Good Sequences

Let $k$ be a fixed positive integer. Let a sequence of positive integers with odd sum $(a_1,\ldots,a_n)$ be called good if for all integers $1 \leq i \leq n$, we have $\sum_{j \neq i} a_j \geq k$ Now ...
1
vote
1answer
70 views

Generating Explicit function from Recursive Equations with Quadratic

Given the recursive function: $$ U(0)=2\\ U(n)={U(n-1)}^{2}+1 $$ How do I generate a explicit function? Please and Thank you!
2
votes
0answers
66 views

Setting up a recurrence for Odd-Even Mergesort

Given the below algorithm How would one go about setting up a recurrence for both that merging algorithm AND using this "new" merging algorithm in a traditional merge sort? What I've tried For ...
1
vote
0answers
124 views

Setting up and solving a recurrence relation

Assume we have two lists, $A$ and $B$; both are sorted lists each with $n$ elements (assume $n$ is a power of 2). We want to recursively merge the odd-indexed elements from each list: merge $a_1, ...
0
votes
1answer
54 views

how to determine maximum length of chain of tail-to-head connections in a given word list

Given a finite set of words, I wish to to write an algorithm which will create a chain of words, where the tail (last letter) of a word n will be the same as the ...
0
votes
2answers
83 views

Converting from base 2 to base 10 through division [closed]

I'm having hard time because of this exercise, I have to implement an algorithm that repeatedly, through continuos divisions, from the remaining of the divisions I can find(looking backward the ...