The 2024 Developer Survey results are live! See the results

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,570
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 ...
48 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
43 views

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
609 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
45 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 ...
135 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
44 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.8k
80 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
67 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
179 views

...
• 59
1 vote
89 views