Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
606 questions
1
vote
2
answers
153
views
How to prove $T(n) = 2T(\lfloor\frac{n}{2}\rfloor) + n$ is $\Omega(n\log n)$?
I know how to prove for $O(n\log n)$, but I'm hitting a roadblock with this one. Here's what I've tried:
The hypothesis is that there exists some $c > 0$ so that $T(n) \geq cn \log n $, by assuming ...
- 11
0
votes
0
answers
40
views
Are there known formal systems where logic and operators emerge purely from recursive structure?
I’m exploring whether there are any existing formal systems that do not assume logic, types, or operators, but instead allow them to emerge solely from recursive structural transformations.
In the ...
0
votes
0
answers
52
views
0
votes
1
answer
115
views
Finding $c$ and $n_0$ for a recursive equation without a base case
I'm trying to find a solution to the following exercise:
Find constants $n_0$ and $c$ such that for all $n \ge n_0,\hskip 1ex T(n) \le cn\log n$ where
$$T(n) = T\left(\frac{3}{4}n\right) + T\left(\...
- 103
0
votes
1
answer
99
views
How to convert Hyperoperation from recursion to iteration?
I’ve been exploring the hyperoperation sequence, which is typically defined recursively.
According to the same source, hyperoperations can be expressed using iteration, but the examples still appear ...
0
votes
1
answer
68
views
Why doesn't this recursive Fibonacci function in Python give me a recursion depth error?
I have the following Python (3.12) code for finding Fibonacci numbers recursively, and keeping track of how many times the function is called.
...
- 103
1
vote
2
answers
126
views
Calculating complexity for recursive functions with substitution method (Big O notation)
$$
T(n) = \begin{cases}
4T(\frac n 2) + \Theta(n) & n \gt 1\\
1 & n \le 1
\end{cases}
$$
I have to calculate the complexity of an algorithm taking time according to above equations using ...
- 11
0
votes
1
answer
64
views
Bellman Ford: Why do we need to use the same vertex with edgesAllowed - 1 in the bellman ford recursive recurrence
So below is the usual bellman ford recurrence
But why do we need to make a call to OPT(v, i-1) given that the shortest path to the vertex v must include the neighbouring vertex u in its shortest path ...
- 11
0
votes
2
answers
85
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, ...
- 1,592
0
votes
1
answer
113
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 ...
- 1
1
vote
1
answer
98
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, ...
- 111
3
votes
1
answer
648
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 ...
- 133
-4
votes
1
answer
90
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 ...
0
votes
1
answer
389
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 ...
- 101
1
vote
0
answers
77
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 ...
- 14k