# Questions tagged [recursion]

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

600 questions
Filter by
Sorted by
Tagged with
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, ...
• 1,568
15 views

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 ...
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 ...
1 vote
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, ...
• 111
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 ...
• 133
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 ...
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 ...
• 101
1 vote
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 ...
• 13.6k
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 ...
1 vote
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,...
135 views

...
• 59
1 vote
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 ...
• 59
177 views

...
• 59
1 vote
86 views