Skip to main content

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
2 answers
40 views

What is the complexity of this tree recursive integer replacement algorithm?

LeetCode has an Integer Replacement problem defined as follows: Given a positive integer $n$, you can apply one of the following operations: If $n$ is even, replace $n$ with $n / 2$. If $n$ is odd, ...
Ellen Spertus's user avatar
0 votes
0 answers
15 views

Incorrect integration results in Adaptive Quadrature routine with periodic functions

I have just finished writing an iterative Adaptive Quadrature routine in C++ that uses the trapezium rule as a base. I plan on writing one using Simpson's rule next. The routine is quite simple. The ...
Gregor Hartl Watters's user avatar
0 votes
1 answer
46 views

Big O notation of T(n) = T(n/2) + O(log n) using master theorem?

I am aware that the algorithm has 1 recursive call of size n/2 and the non-recursive part takes O(log n) time. Master theorem formula is T(n) = aT(n/b) + O(n^d). In this case a = 1, b = 2, but I am ...
inkwad's user avatar
  • 1
1 vote
1 answer
42 views

Algorithms by Dasgupta-Papadimitriou-Vazirani Prologue confusion

We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly proportional to n; this is not too hard to understand if you think back to the gradeschool procedure for addition, ...
Bob Marley's user avatar
3 votes
1 answer
607 views

Can the minimisation operation be seen from a programming language perspective?

If $f$ is a total function $\mathbb N^k\to\mathbb N$, and $g$ is a total function $\mathbb N^{k+2}\to\mathbb N$, then we say that $h:\mathbb N^{k+1}\to\mathbb N$ is definable by primitive recursion ...
Joe's user avatar
  • 133
-4 votes
1 answer
43 views

Why is incompleteness important?

Or take Russel's paradox. Either the barber does or doesn't shave himself -- that's all there is. How you describe it is an artificial construct. Godel's theorem is like dividing by zero and declaring ...
Jess Fuckett's user avatar
0 votes
1 answer
110 views

Number of ways in which a '?' in a given string can be replaced with numbers from [0-9]

I came across this interesting problem in a test and I couldn't complete it. There is a string given s which can consists of numbers between 0-9 and '?'. In place of '?' we can insert any of the ...
ABGR's user avatar
  • 101
1 vote
0 answers
43 views

Bottom-up well-balanced mergesort

If you implement mergesort top-down you can always split the input of length $n$ into one of length $\lfloor n / 2\rfloor$ and one of length $\lceil n / 2 \rceil$. This ensures that all merges are ...
orlp's user avatar
  • 13.6k
2 votes
1 answer
77 views

How to solve the recurrence $ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $ in terms of $\Theta$?

I'm attempting to solve the recurrence relation: $$ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $$ in terms of its asymptotic behavior ($\Theta$), specifically using the first case of the ...
Ferran Gonzalez's user avatar
1 vote
2 answers
59 views

How to Solve the Recurrence Relation $T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$ in terms of $\Theta$?

The provided recurrence relation is as follows: $$ T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2 $$ The goal is to express the solution in terms of the asymptotic notation $\Theta$. Unfortunately,...
Ferran Gonzalez's user avatar
0 votes
1 answer
135 views

what is the complexity of this sorting algorithm?

...
Arugo's user avatar
  • 59
1 vote
1 answer
106 views

Complexity of recursive function using Master theorem

this code aims to determine whether there exists a contiguous subarray starting from index 0 in the given array A whose elements sum up to the target value S. can we apply Master theorem to find out ...
Arugo's user avatar
  • 59
2 votes
2 answers
177 views

What is the Time Complexity of this Slow Sorting Algorithm?

...
Arugo's user avatar
  • 59
1 vote
2 answers
86 views

Bound $T$ asymptotically tight | Recursive trees

Let $\alpha \in (0, 1),\space l \geq 2$ and $T: \mathbb{N}\rightarrow\mathbb{R}^+$ such that, $T(n) = \begin{cases} n^l + T(\alpha n) + T((1-\alpha)n) & : n > 1 \\1 : n=1 \end{cases}$ Bound $...
X4J's user avatar
  • 113
0 votes
0 answers
41 views

Calculating Runtime Complexity: Recursion + Memoization vs Dynamic Programming (with example)

For cases where recursion is used as well as memoization (so that a number of subtrees of what would otherwise be the overall recursive call tree are each replaced to be ...
mishar's user avatar
  • 101
0 votes
1 answer
38 views

What is the "big theta" order of the solution of T_n = T_(n/2) + log n, n > 0?

What method(s) could be used to solve this? I am still new to this stuff and would appreciate detailed justification for every step as well as some intuition and the examination of all possible viable ...
user79644's user avatar
3 votes
1 answer
84 views

Useful algorithm not primitive recursive

The Ackermann function is the textbook example of a function which is total recursive but not primitive recursive. If we want to implement it in some programming language we will need to use a priori ...
Weier's user avatar
  • 231
0 votes
0 answers
32 views

USACO Ski Course Design

So I was doing this problem, but it led me to a different solution. The actual solution is this: Problem - Farmer John has N hills on his farm (1 <= N <= 1,000), each with an integer elevation ...
AdsDeWorst's user avatar
0 votes
4 answers
400 views

Find median in a sorted matrix

Suppose we are given a $n\times n$ matrix that is sorted row-wise and column-wise. We want to find the median in $\mathcal{O}(n\log{n})$. This is my approach: We know median is such element that is ...
Mason Rashford's user avatar
1 vote
1 answer
111 views

Restore the original array after merge Sort based on it's steps

i'm trying to write an algorithm to reconstruct the original array from the sorted one. considering input value is a string of 1s and 2s which 1 means in merging part of merge sort, element from left ...
vhd's user avatar
  • 45
2 votes
0 answers
80 views

Implementation of the divide-and-conquer principle for a specific summation formula

I have found two formulas in the work on pages 5 and 6, of which I am trying to develop a recursive implementation. The similarity to the DFT or FFT might be useful here. I divide this question into ...
TreeBook1's user avatar
0 votes
2 answers
63 views

Trying to implement BFS and I am stuck

I am trying to write down a code which would blindly search for a condition using breadth first search.I have been thinking of it for quite some time and I cant figure out how to continue. On the one ...
Root Groves's user avatar
0 votes
0 answers
14 views

Better implementations for this dynamic program to solve optimization problem?

In the code below, I describe a problem and provide a backtracking implementation in Python that solves it: ...
lafinur's user avatar
  • 195
0 votes
0 answers
56 views

Similar problem to Knight's tour

You have board size and one Knight but what is different is that when you move it you have to duplicate the knight and the 2 duplicates have to be in valid position from the knight This gets repeated ...
KnightsProblem's user avatar
1 vote
1 answer
48 views

Complexity of simulations in simulations

This video of a group, who simulated (a very simple version of) Minecraft inside Minecraft itself got me thinking about the performance of such setups. Another example to what I'm referring to, would ...
SmallestUncomputableNumber's user avatar
0 votes
2 answers
54 views

Prove $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(n\log^2{n})$ using induction

Please first take a brief look at my previous question. Here I want to do something similar but for $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})$. I know the answer is $T(n)=\Theta(n\log^2{n})$ and I want ...
Mason Rashford's user avatar
2 votes
1 answer
68 views

Checking equality of self-referential lists

Define that an srlist ("self-referential list") over $X$ consists of a list of elements of $X \sqcup \mathrm{srlist}(X).$ So basically, the items can be primitive values, or further self-...
SocraticMathTutor's user avatar
1 vote
4 answers
337 views

Understanding the Recursive Algorithm for Integer Division

In my reference, Page 26, Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, a division algorithm is give as, \begin{align} &\text{function divide}(x, y)\\\\ &\...
Sooraj S's user avatar
  • 139
1 vote
2 answers
127 views

Diffucuty in understanding code after a recursive call

This is an example algorithm of a recursive insertion sort I'm trying to understand. I've have tried understanding this with the help of print statements (which I've commented). ...
river_bell's user avatar
1 vote
1 answer
59 views

Are there situations where we can decrease the time complexity of a program by increasing its ordinal complexity?

Are there (interesting) situations where we can decrease the time complexity of a program by increasing its ordinal complexity? For example, is it possible to find a primitive recursive function such ...
agemO's user avatar
  • 177
0 votes
3 answers
154 views

When to do proof by structural induction Vs defining a recursive function?

I'm trying to isolate the key differences between induction and recursion so that I am able to know when to use one over the other. From my understanding, both can be used to prove properties about ...
newlogic's user avatar
  • 165
0 votes
2 answers
38 views

Can proofs by induction be achieved by defining a recursive function between two recursive objects?

I have two types of objects, X and Y, each are recursive structures, and contain different structures sets of tuples containing sets.. etc. The number of elements in X and Y are is the same. I need to ...
newlogic's user avatar
  • 165
1 vote
3 answers
78 views

Having trouble on logic behind recursion

I am struggling to write my own recursive function.I understand how to find the base case but I cant find easily the pattern on the relationship between 2 complicated cases.Do you know any website ...
Cerise's user avatar
  • 153
0 votes
1 answer
49 views

Are recursive Horn clauses first order?

My understanding is that recursive definitions are considered second-order since they require the fixpoint operator in order to be formulated as "true" definitions. This is even though they ...
Motorhead's user avatar
  • 282
0 votes
1 answer
160 views

Change of associativity for a given right-recursive grammar

In section 3.7.1, of the book titled: Compiler design in C, by Allen I. Holub (made available freely online, by the author here, & the page #19 of errata, here), have on page #176, the mention of ...
jiten's user avatar
  • 187
0 votes
1 answer
81 views

Is my mathematical representation of search in binary search tree correct?

You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node's value equals <...
ilovewt's user avatar
  • 113
1 vote
1 answer
94 views

Understanding the Internal Stack Frames in a Recursive Function Call

I'm trying to understand how the system's call stack works internally when a recursive function is called. Specifically, I'm looking at a function that computes the maximum depth of a binary tree ...
ilovewt's user avatar
  • 113
0 votes
1 answer
51 views

Binary search calculating complexity big o

I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book : ...
LeoC's user avatar
  • 1
0 votes
2 answers
95 views

Finding asymptotically tight upper bound of a recursion relation

Find an asymptotic tight upper bound for the following recursion relation: $$T(n)=5T(\frac{n}{5})+\log^2(n)$$ I tried to solve it by applying iteration: $$T(n)=5T(\frac{n}{5})+\log^2(n)=5(5T(\frac{n}{...
GBA's user avatar
  • 109
-2 votes
1 answer
60 views

Programs with feedback?

Suppose we have a program like this: ...
Volpina's user avatar
  • 97
0 votes
1 answer
38 views

Axiomatically, what characterizes “recursion”?

My question is admittedly simple, but the desire is to have an insightful view on it behind a conventional definition. In different foundational or axiomatic systems, I have come to consider “...
Julius Hamilton's user avatar
2 votes
2 answers
108 views

Justification for the properties of algorithmic recurrences in 'Introduction to Algorithms' (CLRS, 4e)

The fourth edition of 'Introduction to Algorithms' defines algorithmic recurrences on page 77 as follows: **Algorithmic recurrences [...] A recurrence is algorithmic, if for every sufficiently large ...
user51462's user avatar
  • 123
0 votes
2 answers
72 views

Clarification of divide-and-conquer recurrence explanation in 'Introduction to Algorithms' (CLRS)

The following excerpt is from page 39 of the 4th edition of 'Introduction to Algorithms' (emphasis added): 2.3.2 Analyzing divide-and-conquer algorithms [...] A recurrence for the running time of a ...
user51462's user avatar
  • 123
0 votes
1 answer
130 views

How to Remove Left Recursion from this Grammar?

How to remove left recursion in the following Grammar: S→Bb/a B→Bc/Sd/e Im new to this, below is the way I'm doing it: ...
whoAsked's user avatar
0 votes
1 answer
76 views

How is there a paradox in the halting problem when you can trace it and it's very clearly non-halting?

Here's Alan Turing's halting problem in pseudocode: ...
Curious cat's user avatar
0 votes
1 answer
88 views

How to derive time complexity of the Recurrence Relation - T(n,m) = T(n-1,m) + T(n,m-1) + c

I know that, T(n,m) = T(n-1,m) + T(n,m-1) + c it's the recurrence equation of Longest Common Subsequence algorithm. And the time complexity of the LCS in case of recursive method is O(2^n+m). The base ...
Samiddha 's user avatar
0 votes
2 answers
245 views

Complexity of generating all subsets of size $k$ using recursion

What is the complexity of the following (Python) code, that builds the list L of all subsets of size $k$ of a given set? ...
Greg82's user avatar
  • 125
0 votes
0 answers
32 views

Does a bijective function exists behind every recurrence relation?

Consider these 2 questions where recurrence relations can be applied: Q1) Given an (nxm) where n denotes rows and m denotes columns of a grid, find the number of unique paths ($a_{n,m}$) that goes ...
rustlecho's user avatar
0 votes
0 answers
34 views

Is recursiveness always from bottom to top?

Lets assume dir a has dir b which has dir c. In a recursive deletion of these directories we ...
obligatory's user avatar
0 votes
1 answer
90 views

Complexity of recursive function that calls itself with it's own return value

Given the following code: int f3(int n) { if(n <= 2) return 1; f3(1 + f3(n-2)); return n - 1; } I was trying to find the time complexity and I got this ...
complexity's user avatar

1
2 3 4 5
12