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
votes
0answers
35 views

form sub-array from an array

I have an array A = (0,1,0,1,1,2,0,1) where A[i] = (1.....n). I need to find intervals of array index which contain all three numbers {0,1,2} i.e the above array can have many sub-arrays. If we ...
0
votes
1answer
30 views

How can we get upper bound in terms of Big Oh notation using Master theorem?

The recursion is: T(n) = 5T(n/2) + O(n) I solved for the time complexity using Master theorem and found Θ(n^2). but, the question has asked to find the upper bound ...
0
votes
1answer
40 views

How does primitive recursion handle mutual recursion?

My intuition is that you can't call a function that has not yet been defined, although I have yet to find a source confirming this. Is this true? Thanks, friends :)
0
votes
0answers
33 views

Solving $T(n) = T(0.01n) + T(0.99n) + cn$ [duplicate]

How to solve the below relation? $$ T(n) = T(0.01n) + T(0.99n) + cn $$ This will not be a balanced tree. For $k$ levels I have something like $\bigl(\frac{1}{100} + \frac{99}{100}\bigr)^k \cdot cn$. I ...
0
votes
1answer
24 views

Recursive Bijections Between Countably Infinite Sets

The textbook I am currently studying (Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi) uses the term 'recursive bijection'. In this context I believe that recursive refers ...
0
votes
1answer
60 views

Is top-down dynamic programming always recursive?

I think top-down dynamic programming is mostly recursive (at least when we use memoization). For instance, solving the rod-cutting problem by this algorithm: ...
1
vote
1answer
61 views

Making use of one function to recursively find n/3 of another

Given an algorithm M that computes the median of an array A in O(n) time, describe an O(n) algorithm to repeatedly call M in order to find the element of rank n/3 in A. This is a problem I am tasked ...
2
votes
1answer
44 views

Are recursion and a stack equivalent in terms of inplementing DFS?

It is well known that DFS can be implemented either with recursion or a stack, and that both approaches are equivalent, but how far can we take that statement? Consider the following LeetCode problem: ...
0
votes
0answers
50 views

is there a theory consider on infinitely many recursion?

of course there is a theory that how many recursive calling the same system to solve problems, this theory is "recursion theory", If i know correctly. and recursion theory is computability ...
1
vote
1answer
44 views

How to convert any recursive solution to a Dynamic programming table? Is there any tricks/tips to follow?

I've been able to form a recurrence relation with memoization in a recursive approach for most problems but the online coding rounds exceed the time limit or stack overflow occurs in all these ...
0
votes
1answer
28 views

Recursive Prefix-Sums K times

I have been wondering about the following question for quite some time: You are given an array $x$. Define f(x) as the prefix sums of this array. For example, f([1,0,1]) = [1,1,2] and f(f([1,0,1])) = [...
0
votes
1answer
53 views

Tic-Tac-Toe in PSPACE

Why is a game like Tic-Tac-Toe in PSPACE? For example for a nxn grid you have nxn! possible game tree paths (duplicates and illegal moves aside), then don't you need (n^2)! memory slots?
2
votes
0answers
35 views

What are the fixed-points of the Y combinator?

Since the Y combinator itself is a function (albeit a higher-order one), I was wondering what the fixed-points of Y itself are.
0
votes
1answer
72 views

Multiplying two integers by dividing each into 3 parts

Integer Multiplication: $x$ and $y$ are two n-bit integers, where $n=3^k$ for some $k>0$. We break $x$ into three parts $a$, $b$, $c$, each with $n/3$ bits; and $y$ into three parts $d$, $e$, $f$, ...
1
vote
1answer
674 views

Is there a better way to optimize my algorithm for maximizing order volume?

I'm trying to find an efficient algorithm to solve the following ... During the day, a supermarket will receive calls from customers who want to place orders. The supermarket manager knows in advance ...
0
votes
1answer
41 views

Question on Erickson 'momselect' algorithm

In the Erickson Algorithms textbook (file:///C:/Users/G068078/OneDrive%20-%20Kaiser%20Permanente/Algorithms_Technique_and_Theory_CS_388G/Undergraduate_CS331/Algorithms-JeffE.pdf) it has pseudocode for ...
1
vote
0answers
85 views

Recursion analysis using Master Theorem

I have the following algorithm: ...
2
votes
1answer
40 views

Calculate the number of "count inversions" of sub arrays

Recently, I encountered the following problem: Given an array $A$ of length $n$ $(0\le n\le 2^{17})$. Let $f(l, r, x)$ denotes the number of occurrences of $x$ in the subarray $a[l\ldots r]$. Find ...
0
votes
0answers
52 views

Total work done at a recursion tree level

In the proof of Master theorem in Dasgupta's Algorithms the author says that the total work done at a recursion tree level is $$a^k \times O\left(\frac{n}{b^k}\right)^d$$ where $a$ is the branching ...
-3
votes
2answers
43 views

Solve $\sum_{i=0}^{\log_3 n-1}i\times 3^i$

I want to find the answer for $$\sum_{i=0}^{\log_3 n-1}i\times 3^i$$ Can you please explain? I this a geometric series?
0
votes
1answer
43 views

How to prove that this language is not recursive enumerable?

I need to prove that the following language is not recursively enumerable, while its compliment is recursive enumerable: $L := \{w \in \{0,1\}^* |$ TM $M$ with $w = \langle $ M $\rangle$ does not ...
1
vote
0answers
11 views

Heuristics to transform a recursively enumerable set into a diophantine set

The class of recursively enumerable sets is equal to the class of Diophantine sets. Given a recursive function, is there a way to produce a diophantine equation such that the trace of calls to the ...
0
votes
1answer
37 views

Are the definitions of loop in CS and in programming (standard/common) identical?

Are the definitions of loop in CS and in programming (standard/common) identical? If not, what is the main difference / what are the main differences?
1
vote
2answers
240 views

Why is there no "traditional"-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?

Why is there no algebraic definition of algorithm besides recursive functions? If I'm wrong, what is the matheist definition of algorithm that you've ever seen in a paper and can you provide a link? ...
0
votes
0answers
28 views

Recursive approach of longest common subsequence

I tried to solve Longest common subsequence problem using recursion, however as I later discovered, my thinking approach was wrong. I took 2 strings say s1 and s2 with lengths l1 and l2, s1="...
1
vote
1answer
39 views

How to perform AND on binary "recursive repeating sequences"?

Suppose, we have a two binary sequences, encoded as "recursive repeating sequences" (I don't know exactly how to name them). Each sequence can contain other sequences and has number related ...
1
vote
1answer
22 views

Induction on recursive formula

Okay so I have this recursive formula $T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2*O\left(1\right) \ \ \ ➜ \ \ \ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\...
-1
votes
1answer
50 views

Solve the following recurrence

I'm trying to solve this the recurrence : $$ T(n)=\begin{cases} 1, & \text{ if } n = 1 \\ T(n-1) +n(n-1), & \text{ if } n \geq 2 \end{cases} $$
1
vote
1answer
49 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
15 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
51 views
0
votes
0answers
12 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
43 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
40 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
32 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
23 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
21 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
45 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
vote
2answers
56 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
50 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
36 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
40 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
25 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
36 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
246 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
30 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
34 views

Difference between Recursion Tree & Binary Tree

What's the difference? is a Recursion tree private case of Binary tree?
1
vote
1answer
110 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
35 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
2 3 4 5
11