Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
6
votes
4answers
107 views
Computing how many distinct digital products are below $10^n$
Given a number $n$, its digital product is the product of its digit. So the digital product of $15$ is $1\times 5=5$, and the digital product of $760$ is $0$, etc.
I recently saw a nice video on ...
0
votes
1answer
28 views
A specific and interesting recurrence relation
Let f and g be increasing functions such that the sets {f(1),f(2),...} and {g(1),g(2),...} partition the positive integers. Suppose that f and g are related by the condition g(n)=f(f(n))+1 for all $n&...
-1
votes
3answers
27 views
Explicit form of $ b_1= 2, b_k = b_{k-1} + 2\cdot 3^k$ for all integers $ k\ge 2 $ [closed]
As the title says, I need to find the explicit form of the recursive sequence defined above, and I am very stuck on this.
1
vote
3answers
40 views
Summation formula for this?
I have found the following summation formula based on a recurrence. It supposes $n = 2^k$ where k is an integer. I've intuitively discovered that the following closed form may be true (following the ...
0
votes
1answer
33 views
How many unlucky numbers in segment $[a;b]$
Some numbers are called unlucky if their decimal representation contain number $5$.
For example: $123456,245,1555$ are unlucky numbers and $111,123,147$ are not unlucky numbers.
In how many unlucky ...
0
votes
0answers
25 views
finding the recursive function for given code
Hey guys, can you give me some guidelines on how to get through questions like this, and help get the closed formula T(n) of the function?
0
votes
1answer
17 views
Heapsort using MaxHeap and MinHeap
As I read in Introduction To Algorithms [3rd edition]:
MaxHeap is used to sort an array into ascending order, while MinHeap is used to sort an array into descending order.
And the tree below can be ...
0
votes
1answer
10 views
Recursive Algorithms - Number of Comparisons - Time Complexity Functions
My text is not exactly straightforward in this section and I'm struggling to figure out how to do this problem:
There isn't anything in the book which explains how to find the number of comparisons ...
0
votes
1answer
22 views
Time Complexity of CLRS Optimal Parenthesis Algorithm
I am reading the Introduction to Algorithms CLRS book, and I am unsure about the time complexity of one of the algorithms that is a recursive algorithm that calls itself twice. This chain matrix ...
0
votes
0answers
27 views
Partition problem where partition are in increasing order.
For given $n$ and $S$, how many possible combinations are there such that:
$x_1 + x_2 + .. + x_n = S $ $\forall i, x_i \leq x_{i+1}$ $\&$ $x_i \geq 1$
For example, if $n$ = 3 and $S$ = 5, there ...
1
vote
0answers
14 views
Intro to Metamathematics Kleene $\S54$ Lemma IId
In this section, Kleene builds a formal system for primitive recursive functions. The beginning of the proof for lemma IId is skipped because it comes for general properties, but I must be missing ...
0
votes
0answers
32 views
Hull-Dobell theorem for linear congruential algorithm
Hull-Dobell theorem says for $x_{n+1}= ax_{n}+c \, mod\, m$ if c ≠ 0, correctly chosen parameters allow a period equal to m, for all seed values. This will occur if and only if
c and m are relatively ...
-1
votes
0answers
16 views
Longest increasing subarray with a recursive function
Input : 1, 9, 2, 7, 20, 13, 50
Output : 2, 7, 20
So far, I got a iterative function.
...
0
votes
0answers
11 views
Extension of the Clenshaw Recurrence Formula
I am wondering if the Clenshaw Recurrence Formula Link, which is used to evaluate a sum
$$f(x)=\sum_{k=0}^N c_k\,F_k(x)$$
when $F_k(x)$ obeys the recurrence relation
$$F_{n+1}(x)=\alpha(n,x)\,F_{n}(...
0
votes
1answer
39 views
Calculate the running time of the code snippet below
for (i=2*n; i>=1; i=i-1)
for (j=1; j<=i; j=j+1)
for (k=1; k<=j; k=k*3)
print(“hello”)
I sopused that its N^5 but Im not sure
1
vote
0answers
10 views
Question about Proof: Semi-decidable => Recursively Enumerable
Def. A set A is recursively enumerable if $A = \emptyset$ or if there exists a total computable function $g$ such that $A = R(g)= \{z | \exists x. g(x) = z \}$.
Def. A set A is semi-decidable if ...
-1
votes
0answers
117 views
Algorithm to allow player 1 to force a win
Two players play a game, starting with three piles of $n$ pebbles
each. Players alternate turns. On each turn, a player may do one of the following:
take one pebble from any pile
take two pebbles ...
0
votes
0answers
44 views
Closed form of generalized Josephus problem
I have to solve Josephus problem where every 5th man gets killed and I have to find out the living person number and $n = 10000$
The generalized solution of Josephus problem is
$J(n,k) = ((J(n-1,...
0
votes
0answers
7 views
Finding Volatility of multiple numbers
I have set of few numbers like below ranging from -9 to 9 ,
If set of numbers has more difference to each other than volatility should be very high , if all numbers has very short difference , ...
2
votes
2answers
42 views
Does this recursive function have a function in terms of n?
I am trying to convert the following recursive function to a non-recursive equation:
$$f(2) = 2$$
For $n>2$:
$$f(n)=nf(n-1)+n$$
I have calculated the results for n=2 through to n=9:
$$\begin{...
0
votes
1answer
27 views
How to solve equations using big $\Theta$
How would I prove that the statement
$$10n^3 +3n = \Theta(n^3)$$
is true/false?
1
vote
1answer
32 views
Using the Master Theorem to solve a recurrence
I have the following recurrence relation, which I am trying to solve using the Master Theorem:
$$
T(n) = 2T(n/2) + n^{\frac 12} + \log n
$$
Comparing the above recurrence to the recurrence of the form:...
0
votes
0answers
29 views
Solving a recurrence using the Master Theorem
I have the following recurrence relation, which I'm trying to solve using the Master Theorem:
T(n) = 2T(n/2) + n(2 + sin(n))
I compared this recurrence to the one of the following form:
T(n) = aT(n/...
0
votes
1answer
51 views
how to work out a computer program running time
I have a question and im not sure how to tackle it....
algorithms have running times proportional to the following functions of the input size, denoted N:
$N^2$
$2^N$
In one minute of computing ...
-1
votes
1answer
19 views
Algorithm to solve systems of first order “triangular” linear difference equations
I have a system of first order linear difference equations, which look like this:
\begin{align*}
\vec{x_n} = A \vec{x_{n-1}} + \vec{b}
\end{align*}
Where $A$ is an upper triangular matrix.
What ...
3
votes
0answers
48 views
Solving recurrences using substitution method
I have given
$$
T(n)= \begin{cases} T(n/3)+T(2n/3)+n,\quad &n>1 \\
1, \quad &n=1
\end{cases}
$$
I tried it again and again but couldn't think beyond,
$$
T(n)=T(n/27)+3T(...
1
vote
0answers
24 views
How to prove that a recursive function with inner summation is approximately equal to some closed-form equation?
The following problem is taken from an algorithms textbook(specifically, in the context of complexity analysis of recursive algorithms.)
Starting from the equation:
$$nf(n) = n(n-1) + 2 \sum_{k=1}...
1
vote
2answers
73 views
Leaving recurrence summation in terms of $k$, $\sum_{i=0}^{k-1}\frac{3^i\sqrt{\frac n{3^i}}}{\log\frac n{3^i}}$
I have an exercise where I need to use the substitution method to solve the following recurrence and determine their corresponding complexity.
$$t(n)=3t(n/3) + \frac{\sqrt n}{\log n}$$
After some ...
0
votes
1answer
18 views
Find $F_{2^n}$ for polynomial time.
You have the nonnegative integers $a_1, a_2, ..., a_k, F_1, F_2, ...,F_k$. Consider the sequence $F_n = a_1F_{n - 1} + a_2F_{n - 2} + ... + a_kF_{n - k}, \forall n > k$. Suggest a polynomial ...
0
votes
1answer
25 views
Fractional Knapsack Problem Linear Time
So I came across a solution to the fractional knapsack problem in linear time here:
http://algo2.iti.kit.edu/sanders/courses/algdat03/sol12.pdf
I'm not sure I understand the algorithm given. We ...
0
votes
1answer
30 views
Understanding the Master Theorem - Determining the levels of recursion
I am trying to understand the proof for the Master Theorem. I have started by unwinding the following recurrence in order to find the total running time of an algorithm whose time complexity can be ...
1
vote
0answers
15 views
Divided Differences expanded form definition.
From definition of divided differences we have that $$f[x_0,\cdots,x_n]=\sum_{j=0}^n\frac{f(x_j)}{\Pi_{{k\in\{0,\cdots,n\}-\{j\}}}(x_j-x_k)} $$
It makes completely sense to have $k\neq j$ otherwise ...
2
votes
1answer
35 views
Optimal permutation for differential storage
This is a practical problem I encountered recently. I'm convinced that it has been solved before, however I don't know where to start looking as I'm unfamiliar with all the terminology involved. Hope ...
2
votes
2answers
110 views
is there a faster method to calculate $1/x$ ($x$ an integer) than this?
I gave this stackexchange a second go. Is there a faster way to calculate $1/x$ than the following:
Calculate $100/x$ (.or other arbitrary positive power of $10$) with remainder
Write multiplier in ...
1
vote
1answer
21 views
Mathematical Induction for a defined Fibonacci Function
I'm a bit stuck on this problem and can't figure out how to proceed. We have the following Fib. recurrence given to us:
$f(0;a,b) = a;$
$f(1;a,b) = b;$
$f(n;a,b)=f(n-1;b, a+b)$
The problem defines ...
2
votes
0answers
42 views
How to determine how fast something is going towards infinity?
Just for a little bit of information I'm more of a programmer and less a mathematician so if some of my terms seem out of place it is due to a lack for formal training in Math.
While working on my ...
0
votes
0answers
69 views
Longest Increasing Subsequence Using Divide-And-Conquer
I'm required to solve the LIS problem using Divide-and-Conquer. The hint provided is the following: For each position in the array find the
cardinality of the longest sequence that ends up with it, ...
0
votes
2answers
34 views
Sinusoidal Generation in Recursive Algorithm
I need to generate sinusoidal values for varying frequencies. I'm making a DTMF tone generator but I must generate my own values of sine using recursive algorithms. The exact wording of how I'm ...
0
votes
3answers
78 views
Solving a recurrence relation: can't figure out how to convert from summation
I am really struggling to solve this recurrence.
$$
T(n) = T(\sqrt{n}) + n.
$$
I am asked to give asymptotic upper and lower bounds for $T(n)$. I am free to use any method to arrive at my answer, ...
1
vote
1answer
28 views
$(G,\cdot)$ and $M \subseteq G$. Prove that the following algorithm computes the subgroup generated by M.
Let $(G,\cdot)$ be a finite group and $M \subseteq G$, $M\ne \emptyset$.
Prove that the following algorithm computes the subgroup generated by M :
$$S_{0}:=\{{e}\} , H_{0}:=\{{e}\}\\
S_{n+1}:=(S_{n}\...
0
votes
0answers
36 views
How can I compute recursive QR-factorization?
I wonder if it's possible to find the $Q$ and $R$ matrices from this QR-equation with only compute QR at one time only:
$$A = QR$$
if, the first column of $A$ got removed and then a new column got ...
1
vote
1answer
221 views
Variance of parameter estimate using recursive least squares
I am learning about recursive least squares estimation using a forgetting factor $\lambda$ as a tool for treating time variations of model parameters and have become stuck on the following problem.
...
-1
votes
1answer
27 views
show algorithm to compute square root converge. [closed]
Consider the calculating the square root as follow:
Let's say we want to compute square root of $x>0$, pick a number $g_1>0$, then if $|g_1^2-x| < 0.00001$ then done. Else, let $g_2=\frac{g+\...
-1
votes
2answers
119 views
Solve the operations needed for the recursive formula
$f(n) = 1+\frac{1}{n}\sum_{i = 0}^{n - 1} f(i)$
Base case: $f(0) = 0$
how can I solve the recurrence?
0
votes
3answers
38 views
sequence that adds its previous results
Let $x = 0.3$.
The first number of the sequence is $x$.
The second number is the first number + $(0.3\cdot 0.3)$.
The third number is the second number + $(0.3\cdot 0.3\cdot 0.3)$.
This is a ...
0
votes
0answers
22 views
Is there a specific search paradigm for finding pairs in a set?
I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of ...
0
votes
2answers
30 views
What is a goal of Galileo's magnetometer recursive filter
I'm designing the basics of space magnetometer instrument for academic project and I came across a Galileo mission investigation document, with data flow described in chapter 6. As a first ...
1
vote
2answers
49 views
proof that Ackermannfunction is uniquely defined and finding algorithm without recursions to calculate its values
my question is involving the Ackermannfunction.
Let's call a function $a: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ "Ackermannfunktion", if for all $x,y \in \mathbb{N}$ the following ...
0
votes
1answer
36 views
How to prove that class of “recursive” and “recursively enumerable” languages are not equal?
I would like to formulate a formal proof for showing that the classes of recursive and recursively enumerable languages are not equal.
I know that recursive languages are accepted by Turing machines ...
0
votes
1answer
36 views
Recurrence proof by induction
I'm having a hard time to understand how am i supposed to solve this question:
$T(n) = \sqrt{n}T(\sqrt{n})+n$. Prove by induction that $T(n) = \Theta (n \log{(\log{(n)})})$.
These are all the data ...
