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
1
vote
1answer
27 views

Find the minimum cost of adding the elements of a set (greedy algorithm)

I'm VERY stuck with this problem: Given a set (with possible repeated elements), the cost of adding two elements $x, y$ is $x + y$. For example, the possible costs of the next set $\{1,2,5 \}$ are: ...
1
vote
1answer
14 views

can't quit understand one step of the recurrence time complexity calculation

I solved the question T(n) = T(sqrt(n)) + 1 but can't quit understand one step of the solution I don't understand the transition in (1). how did we conclude that T(m) = T(m/2) + 1 from the previous ...
0
votes
0answers
19 views

Recurrence relation of an algorithm

how can I know what are the recursive calls of this algorithm ? in line two there are 2 recursive calls and I don't know how to write this as T(n) for the Recurrence relation. Here is the algorithm :
1
vote
2answers
35 views
0
votes
0answers
8 views

solving 𝑇(𝑛)=𝑇(𝑛/3)+𝑇(𝑛/6)+1 without Akra-bazzi method [duplicate]

I need to find $g(n)$ so that $𝑇(𝑛)=𝑇(𝑛/3)+𝑇(𝑛/6)+1 = \Theta(g(n))$. I know that the recursion tree height, $h$, is $\lg_6{n}\le h \le \lg_3{n}$ and that every level of the tree has at most $2^d$...
1
vote
0answers
40 views

Is there a term for the inverse of a fixed-point operator?

When working with recursion it is often useful to find the least or greatest fixed points of a morphism, often using a fixed-point combinator. When working with recursion schemes, the inverse ...
0
votes
0answers
33 views

substitution method - proving karatsuba algorithm is not O(n)

I want to prove that $T(n) \neq O(n)$ for the Karatsuba algorithm, which has the following recurrence: $$ T(n) = \begin{cases} k_1, & \text{if $n$ = 1} \\ 3T(n/2) + k_2n, & \text{if $n \gt$ 1} ...
0
votes
0answers
23 views

Dynamic Programming, lru-cache, “minimum weight of a number”

I'm struggling with the following problem: The weight of a correct arithmetic expression, consisting only of the strings 1, x, +, is defined as the number of 1s appearing in the expression. Each ...
0
votes
0answers
27 views

Why do online compilers/interpreters use different limits for the maximum recursion depth error?

When using two different online Python compilers/interpreters for executing a program (this one, and this one), I found that both sites showed the maximum recursion depth error at $n = 998$, whereas ...
0
votes
1answer
18 views

What are the guidelines/tips for calculating the complexity of a chained-recursive function?

Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions.. Are there any ...
0
votes
0answers
19 views

I need good book about algorithms, which explains recursion, backtracking and depth first recursion for beginners [duplicate]

I'm learning programming, Python 3 in particular, and I have a good book "Beginning Python - From Novice to Professional" by Magnus Lie Hetland, but the book doesn't explain algorithms at ...
2
votes
1answer
24 views

Code and time complexity of multiplication à la française

This references the multiplication algorithm in Chapter 1 of Algorithms by Dasgupta et al. I am trying to understand how the code for multiplication à la française works from the multiplication by ...
-1
votes
1answer
81 views

What is a loop mathematically?

Here is a word problem For every dollar Ben spent on bagels, David spent 25 cents less. Ben paid $12.50 more than David. How much did they spend in the bagel store together? My programmer mentality ...
1
vote
2answers
36 views

Constant terms at each level of a recursion tree

In CLRS, exercise 4.4-5 the following question is asked: Use a recursion tree to determine a good asymptotic upper bound on the recurrence $$T(n) = T(n-1) + T(n/2) + n$$ In my recursion tree, the ...
1
vote
1answer
39 views

Running time of a function $P$ calling itself via $P(P(n/2))$

int P(int n) { if (n==1) return 1; else return P(P(n/2)); } How will this function P(P(n/2)) be executed and what ...
1
vote
1answer
34 views

How to calculate the basic steps in Fibonacci sequences to get nFn and n^2

I am reading Algorithms by Sanjoy Dasgupta, Umesh Vazirani, Christos Papadimitriou and I am trying to understand how the number of steps $nF_n$ and $n^2$ were calculated. Here's the part of the book ...
1
vote
1answer
28 views

How to prove $T(n) = 2T(n/2) + n/\log(n)$ can't be solved using the Master Theorem?

I have read (in this question) that this recursion can't be solved via Master Theorem. But I couldn't find exact and complete proof why the Master Theorem does not apply.
0
votes
0answers
14 views

It is possible proove the complexity of each query in a Segment Tree to O(log N) with recursion tree

Maybe the title is bad format but, I want to ask if is possible proof the Segment Tree complexity with the recursion tree. In other words I'm making a simple report on segment tree and I want to try ...
0
votes
0answers
27 views

Generalised letrec semantics for mutual recursion

I'm new to system types and I was wondering how mutual recursion is defined through generalized e::= ..|let rec x1=e1 ,...., xn=en in e .What has to be added in the "simple" let rec ...
0
votes
1answer
77 views

Solving the recursive equation $T(n)=T(k)+T(n-k-1)+O(n)$

The question is clear in the title. I am trying to solve this recursion as a part of showing that the worst case of quicksort algorithm occurs when $k=0$, but can't do it. I could do the following ...
0
votes
0answers
23 views

Back Substitution Method for solving recursive equation

Does back substitution method work for any recursive equation? If not is there any generalized form for recursive equation?
2
votes
1answer
28 views

Difference between Recursion Tree & Binary Tree

What's the difference? is a Recursion tree private case of Binary tree?
1
vote
1answer
35 views

Time complexity of a recursive function which generates all combinations of an array

The following function getCombinations, is a recursive function that can be used to generate all combinations of an array. How exactly can we find the time complexity of this function? I would ...
0
votes
1answer
32 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
1answer
27 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{ ...
0
votes
2answers
46 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) $$\...
0
votes
2answers
59 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 ...
0
votes
0answers
22 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: ...
0
votes
0answers
46 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
0answers
30 views

Space usage of recursive functions with no return

Consider an algorithm for reversing a sequence given below: ...
-2
votes
1answer
172 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 ...
2
votes
1answer
55 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
28 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 ...
0
votes
0answers
17 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 ...
3
votes
1answer
71 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
1answer
116 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
37 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
39 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
76 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
56 views
0
votes
0answers
32 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
16 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
112 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
60 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 ...
1
vote
1answer
37 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?
0
votes
1answer
56 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
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
82 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) \...
0
votes
0answers
76 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
2 3 4 5
10