Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
562
questions
0
votes
1
answer
61
views
Need help with recurrence relation and postcondition of a function
I just wanted to make sure I'm on the right track regarding this.
Here's the function that I'm dealing with:
...
1
vote
1
answer
30
views
Membership in 1, 5, 2, 13, 10, ... (recursively defined sequence)
Find if a given integer is in the series $1, 5, 2, 13, 10, \dots$ in the most efficient way, where the sequence is given by
$$
f(n) =
\begin{cases}
1 & n=1, \\
2f(\tfrac{n}{2})+3 & n \text{ ...
- 13
0
votes
2
answers
69
views
Solving $T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n$ without the Master Theorem
I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$
with base case $T(n) = 1$ if $n \leq 1$.
I know that the solution is(with the help of the Master Theorem) $$\...
- 147
0
votes
2
answers
163
views
Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$
Prove by induction that $T(n)=\Theta(n^2 \log_{3}n)$ where
$$T(n)= \begin{cases} 1 & \mbox{if } n=1,\\ 9T(\lceil n/3 \rceil)+n^2 & \mbox{otherwise.} \end{cases}$$
The base case for $n=1$ seems ...
- 147
0
votes
0
answers
76
views
Prove that $T(n)=\omega(n)$?
Edit: can someone provide clear answer with all details
Given:
$T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$
I was asked to find the minimum value for $a$ for which $T(n)=\omega(n)...
1
vote
0
answers
101
views
Space usage of recursive functions with no return
Consider an algorithm for reversing a sequence given below:
...
- 135
-2
votes
1
answer
1k
views
Solving $T(n) = 16T(n/2) + n$
I am trying to solve the following recurrence relation :-
$T(n)=16T(n/2)+n$ using masters theorem. I got $\Theta (n^2)$ (Which matched the first case in the theory) which is wrong, any help with this ...
3
votes
1
answer
171
views
Is well-founded recursion enough for practical total functional programming?
Total functional programming is a paradigm of non-Turing-complete programming languages where any program that type checks is proven to halt.
Well-founded recursion is a recursive definition of a ...
- 3,492
1
vote
1
answer
39
views
Time complexity of binary search
Proposition: The binary search algorithm runs in $O(\log n)$ time for a sorted
sequence with $n$ elements.
When justifying this claim, first we say that with each recursive call the number of ...
- 135
3
votes
1
answer
176
views
Loop optimization of non-tail recursion
When researching how to optimize recursion into loops, I came upon (on Wikipedia) a general rule about this: Whenever a function is in form:
...
- 33
0
votes
1
answer
352
views
Recursive algorithm to find maximum value in 2D array
Imagine a 2D array of size n x m, where every column is a stack of positive values. I am trying to figure out a recursive pseudo code algorithm, where I have a ...
- 11
0
votes
0
answers
351
views
Solve recursive function $T(n) = T(n/3) + T(n/6) + n^{\sqrt{\log{n}}}$
In one of my college assignments, I came up with the following recursive function which I'm asked to solve:
$T(n) = T(n/3) + T(n/6) + n^{\sqrt{\log{n}}}$
I tried a change of the variable or the ...
- 150
2
votes
1
answer
192
views
Solve the recursive function $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$
in one of my college assignments i came up with the following recursive function which I'm ask to solve:
$T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$
I could not use master method on it and it ...
- 150
1
vote
1
answer
411
views
Is "backward substitution" and "backtracking" the same thing?
From my limited knowledge, they both are related to solving recurrence relation.
Solving recurrence relation using backward substitution
Solving recurrence relation using backtracking
Can the terms ...
- 327
1
vote
1
answer
75
views
What is the solve of F(n,n) = F(n-1,n) + F(n, n-1) + 1 Where F(0,a) = 1 and F(a, 0) = 1 for every a
I'm given the following python function:
...
- 150
0
votes
1
answer
47
views
How do I work out the recurrence relation of the given function?
I am looking to find the recurrence relation of the following function:
...
- 146
1
vote
1
answer
1k
views
Recurrence formula for optimal binary search tree
This question is from Section 15.5 of Introduction to Algorithms (third edition).
We are given sequence of keys, $ k = \{ k_{1},k_{2},\dots,k_{n} \}$, where $k_{1}<k_{2} <\dots<k_{n} $.
For ...
- 65
4
votes
1
answer
245
views
Proving O(log n) bound for the number of iterations when we select the average as the pivot
Motivation
So the other day I had fun providing a new solution to this famous question. In the analysis part I showed that my little algorithm has space complexity: ...
- 113
0
votes
0
answers
29
views
what is the complexity of the below code? [duplicate]
I wanted to calculate the complexity of this pseudocode. In my knowledge, it is $n^2$ because the last loop only runs 8 times. I wrote a program to test it tends to run 8^logn (approximately). can you ...
1
vote
1
answer
46
views
A problem about master theorem and recursion [duplicate]
Prove or disprove the following statement:
If $f(n)\in \Omega(n^2)$ and $T(n) = 2T(n/2) + f(n)$ then $T(n) \in O(f(n))$.
I think that the statement is false.
Do you know any counterexamples?
- 9
0
votes
1
answer
74
views
Simplifying $r_n = \max(p_n,r_i+r_{n-i})$ to $r_n = \max(p_i + r_{n-i})$
In CLRS (Intro to algorithms) on page 362, it says equation (1):
$$ r_n = \max(p_n, r_1+r_{n-1},r_2+r_{n-2},\dots,r_{n-1}+r_1) $$
can be simplified to this equation (2):
$$ r_n = \max_{1 \leq i \leq n}...
- 65
1
vote
1
answer
56
views
Does this LCS algo generate all the CS or only all the LCSs?
The Wikipedia article on LCS has an algorithm that backtracks all the LCS strings. This link redirects to the desired bulletin in the article. The C table in the backtrackAll function is pre-...
- 194
0
votes
1
answer
606
views
Algorithm for assigning people to groups
Given a list $L = [1, 2, .., n]$ and a list $C = [(L_i, L_j), ....]$ form a group of pairs $G = g_1, ..., g_{n/2}$ such that:
every element of $L$ is assigned to exactly one group
$g_k = (L_i, L_j) \...
- 371
0
votes
0
answers
431
views
Why the time complexity for following pseudocode is O(n^2)?
So, I was going through the Rod-Cutting problem in the Dynamic Programming section of the Introduction to Algorithms by CLRS.
Here's the rod-cutting problem statement: Given a rod of length n inches ...
- 243
0
votes
1
answer
33
views
Asymptotic runtime of recursive algorithm uisng subsitution method
I need to solve this question using the substitution method:
$T(n) = 3T(n/2)+2n$ if $n>1$ otherwise, $T(n) = 1$
Note: $$\sum_{i=0}^k x^i = \frac{x^{k+1}-1}{x-1}$$
$$a^{\log_b n} = n^{\log_b a}$$
...
1
vote
2
answers
127
views
Closed form of recurrence with two inputs
This question comes from a relatively simple coding challenge at Codesignal, but represents an interesting CS/math puzzle. The question states:
"When a candle finishes burning it leaves a ...
- 13
0
votes
0
answers
90
views
Are some algorithms inherently recursive?
Are some algorithms inherently recursive?
As in, rewriting it in tail-recursive/iterative form with a stack is still needed, and there is no way to do it otherwise.
I am asking because I struggled to ...
- 125
1
vote
1
answer
801
views
Solve Recurrence for $T(n) = 7T(n/7) + n$
I'm trying to solve the recurrence for $T(n) = 7T(n/7) + n$.
I know using Master Theorem it's $O(n\log_7n)$, but I want to solve it by substitution method.
At level $i$, I get: $7^i T(n/7^i) + (n+7n+7^...
- 113
0
votes
0
answers
25
views
Which function results from primitive recursion of the functions g and h?
Which function results from primitive recursion of the functions $g$ and $h$?
$f_1=PR(g,h)$ with $g=succ\circ zero_0, h=zero_2$
$f_2=PR(g,h)$ with $g=zero_0, h=f_1\circ P_1^{(2)}$
$f_3=PR(g,h)$ with $...
- 156
1
vote
1
answer
89
views
Using inductive hypothesis on recurrence relation?
I have a recurrence relation as follows
$$T(n) = 2T(\lfloor n/2\rfloor) + n\log(n)$$
Using the induction hypothesis how do I obtain a relation $T(n)\leq E$ such that $E$ contains neither $T$ nor floor ...
- 11
4
votes
2
answers
211
views
Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2?
The title could be a little bit confusing, and it is not easy to summarize it within a sentence, therefore I will explain it in detail below. If you have any thoughts on optimizing and rephrasing the ...
- 41
0
votes
1
answer
33
views
Show that the inequality holds for all positive integers
$a_1=2,a_2=9,a_n=2a_{n-1}+3a_{n-2}$ for $n>=3$
Show $a_n<3^n$ for all positive integers n
Base case: $a_3 = 2*9+3*2 = 24<=3^3$ is true
Hypothesis: $a_k<=3^k$ for $k\epsilon\mathbb{N}$, ...
- 13
1
vote
1
answer
35
views
Determining which recursive term is bigger if they share the same definition
We are given a recursive definition:
$a_1 = x,\\a_2=y,
\\a_n= c_1a_{n-1}+c_2a_{n-2} \text{ for }n\ge3 $
where $x,y,c_1,c_2,n$ are natural numbers
we are to prove that $a_n \le c_3^n$ for all n
The ...
- 13
2
votes
1
answer
182
views
Why, intuitively, does the Ackermann function require $\mu$-minimisation?
I have read proofs that the function is not primitive recursive and I (think) I understand them. Most I've seen show that the set of functions dominated by the Ackermann are exactly the primitive ...
- 133
2
votes
1
answer
526
views
How to convert a recursive function to a non recursive one using stack while keeping memoization?
Let's say I want to count the number of ways a string can be decoded, once encoding algorithm follows this map: 'a'=>'1', 'b'=>'2', ... 'z'=>'26'.
I could ...
- 21
2
votes
0
answers
122
views
How do you write a python\pseudo code that generates all pair permutations?
What would be a good pseudo code or Python 3 code for the following permutations problem?
Let us define a n-permutation as a bijective function $\pi: \{0,...,n-1\}\rightarrow \{0,...,n-1\} $ and ...
- 21
2
votes
0
answers
109
views
How to prove νX. A × X ≅ (μX. 1 + X) -> A?
How can we prove Stream A = νX. A × X is isomorphic to Nat -> A = (μX. 1 + X) -> A ?
In programming sense, ...
- 121
1
vote
1
answer
47
views
How to solve recursion with two separate converges rates
What is the correct way to solve the following recursion:
$T(n)=T(\lceil\frac{n}{2}\rceil) + T(n-2)$
Or basically any recursion that has two parts which converge in a different rate.
I'm trying to get ...
- 49
0
votes
1
answer
53
views
Is my recursive algorithm for Equivalent Words correct?
Here is my problem.
Problem
Given two words and a dictionary, find out whether the words are equivalent.
Input: The dictionary, D (a set of words), and two words v and w from the dictionary.
Output: A ...
-2
votes
1
answer
3k
views
How to calculate the minimum price required to buy all the stones?
I have shared the question above. My current algorithm does the calculation in O((n^4)*(2^n)).
Can someone please help me out to solve this faster?
2
votes
1
answer
2k
views
How do I calculate the time complexity of this memoized algorithm?
The problem is: count all increasing subsequence of s.
...
0
votes
1
answer
62
views
MAXSAT using dpll algorithm?
It's possible to return from a dpll algorithm M as maximum for MAX-SAT problem?:
I have a sample:
https://gist.github.com/davefernig/e670bda722d558817f2ba0e90ebce66f
we can modify recurrency to return ...
- 133
1
vote
1
answer
85
views
Any reason why Turing Machine would prevail on recursion theory?
Nowadays, most introduction books, videos, and comments about theoretical computer science talk about Turing machines but don't discuss recursion theory anymore. These approaches are known to be ...
0
votes
2
answers
1k
views
Analyzing space complexity of passing data to function by reference
I have some difficulties with understanding the space complexity of the following algorithm.
I've solved this problem subsets on leetcode. I understand why solutions' space complexity would be O(N * 2^...
2
votes
1
answer
126
views
Recurrence relation for the number of "references" to two mutually recursive function
I was going through the Dynamic Programming section of Introduction to Algorithms (2nd Edition) by Cormen et. al. where I came across the following recurrence relations in the context of assembly line ...
- 1,052
0
votes
1
answer
47
views
What is the difference between these two Edit Distance Algorithm
Edit Distance is very well known problem in computer science. Came up with following algorithm after reading through CLRS but it doesn't work. Check the working algorithm below, I couldn't find why ...
- 1
1
vote
0
answers
200
views
What is sideways recursion
A friend of mine is studying business analytics, currently on the topic for Microsoft DAX, but he is very new to the technological field. He mentioned yesterday, during a conversation, the term "...
- 111
0
votes
0
answers
52
views
Big $O$ approximation for $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$
I have the following complexity equation: $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$ with the base case $T(m)=1$.
Is it possible to calculate a big $O$ approximation for such equation? What is the right ...
- 49
2
votes
1
answer
232
views
trouble solving the recurrence 4T(n/2) + n
I am having trouble figuring out how to solve this recurrence problem...
$$
\begin{aligned}
&4T(n/2) + n \\
= &4(4T(n/4) + n/4) + n \\
= &16T(n/4) + 2n \\
= &4^kT(n/2^k) + kn
\end{...
- 133
1
vote
1
answer
991
views
Arbitrary depth nested for-loops without recursion
Suppose I have an array of n values I want to apply nested for-loops over to an arbitrary depth m.
...
- 143