Questions tagged [recursion]

Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.

Filter by
Sorted by
Tagged with
0
votes
1answer
19 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 ...
3
votes
2answers
1k views

Technique for converting recursive DP to iterative DP

I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed). But, I'm unable to convert my recursive code to <...
0
votes
0answers
19 views

Trying to convert algorithm from recursive to iterative

I have this algorithm to sum binary tree branches from leftmost branch to rightmost one, so the solution is an array of sums: ...
-1
votes
0answers
36 views

Recurrence relation $T(n/10) + T(c·n) + n$

Given the following question: $T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$ Using a set of complicated equations I found and proved that $a=9/10$ is the correct answer (for sure) ...
0
votes
0answers
40 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)...
-2
votes
1answer
29 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 ...
1
vote
4answers
621 views

Towers of Hanoi First Move

I've finally more or less understood the recursive algorithm for solving the Towers of Hanoi. My Python code is below. However one thing still bugs me - I can't yet work out how this simple seeming ...
1
vote
0answers
21 views

Space usage of recursive functions with no return

Consider an algorithm for reversing a sequence given below: ...
0
votes
1answer
50 views

How is equation 1 simplified to equation 2 as shown below

In CLRS (Intro to algorithms) on page 362, it says eqn(1) : can be simplified to this equation(2): I would like to know how this simplification was arrived at. It shouldn't necessarily be a formal ...
1
vote
0answers
21 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 ...
1
vote
1answer
37 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-...
0
votes
1answer
426 views

Merge sort and quicksort recursion tree depth

1) I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one/I can do it on a paper, just drawing tree, but what about ...
1
vote
1answer
27 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 ...
2
votes
1answer
50 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: ...
0
votes
0answers
16 views

Upper bound for reccurence relation with two variables, with linear dependency between them

Given the following reccurence relation: $$T(M,k) = T(M-1,k)+T(M-2,k-1)$$ where $T(0,k)=0, T(1,k)=1, T(M,1)=1$ I have $M^k$ as a general upper bound for $T(M,k)$. Now, suppose I want to give an upper ...
0
votes
1answer
36 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 ...
0
votes
0answers
33 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 ...
1
vote
1answer
28 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 ...
0
votes
1answer
33 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 ...
1
vote
1answer
46 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: ...
0
votes
0answers
26 views

Time complexity of a recursive algorithm with two lists as parameters

The goal is to find the function T which describes the time complexity of an algorithm who merges two lists (but the lists are given inversely sorted). The problem is that recursive calls depend on an ...
0
votes
1answer
14 views

How do I work out the recurrence relation of the given function?

I am looking to find the recurrence relation (RR) of the fnA(), but I am unsure how $n$ is to be represented. (More specifically, I am trying to work out the ...
1
vote
1answer
52 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 ...
1
vote
0answers
59 views

Proving a tighter upperbound (big-O) for this problem

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: ...
0
votes
0answers
28 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 ...
0
votes
1answer
494 views

Longest double increasing subsequence (LIS variant)

I'll start with the definitions:Let $S = s_1s_2...s_n$ be a sequence of $n$ integers. A double increasing subsequence of $S$ is a sequence $P=p_1p_2...p_k$ (not necessarily continuous) where for each $...
1
vote
1answer
36 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?
1
vote
1answer
26 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 ...
0
votes
1answer
36 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) \...
-2
votes
1answer
1k 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?
0
votes
0answers
49 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 ...
1
vote
1answer
28 views

Understanding recursion tree for withdrawal formula

$$ T(n) = T(n-a) + T(a) + cn $$ Now the solution says that the height of the tree $(h)$ is: $$ h = \left \lfloor n/a \right \rfloor $$ And I don't understand why. Maybe I didn't understand the ...
1
vote
1answer
59 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 ...
0
votes
1answer
25 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}$$ ...
0
votes
3answers
98 views

How many times in this pseudo-code is the function F called?

For this question, I thought function F called twice but it called three times. Are those three functions were called? F(N), F(K) and F(N-1)? How many times in this pseudo-code is the function F ...
0
votes
0answers
58 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 ...
1
vote
2answers
41 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 ...
2
votes
1answer
42 views

Is this an example of Tail Recursion

As I have read in this answer: What is tail recursion? tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call. Here after the ...
1
vote
1answer
43 views

Using Subset Sum algorithm $O(n)$ times to find the subset

Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given ...
1
vote
1answer
209 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^...
0
votes
0answers
22 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 $...
5
votes
2answers
142 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 ...
16
votes
3answers
14k views

Can a tree be traversed without recursion, stack, or queue, and just a handful of pointers?

Half a decade ago I was sitting in a data structures class where the professor offered extra credit if anyone could traverse a tree without using recursion, a stack, queue, etc. (or any other similar ...
0
votes
1answer
29 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}$, ...
1
vote
1answer
33 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 ...
1
vote
1answer
45 views

How to generate tree variants of a tree using recursion?

I have a tree T, I need to generate all possible variants of T by permuting all its child nodes(please refer the following figure). how can I generate all variants, T, using recursion? any help is ...
2
votes
1answer
64 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 ...
0
votes
1answer
895 views

Prove Recursive formula (Dynamic programming) N(C,i)

I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following ...
0
votes
1answer
37 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 ...
1
vote
2answers
193 views

Pancake Sorting Graph Recursive Definition

I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n>= 4. I can see obviously that, in the case of n=4, there will be 4 rough ...

1
2 3 4 5
10