# Questions tagged [recursion]

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

448 questions
Filter by
Sorted by
Tagged with
46 views

### Recurrence formula for optimal binary search tree

This question is from Section 15.5 of Introduction to Algorithms (third edition). We are given sequence of keys, $k = \{ k_{1},k_{2},\dots,k_{n} \}$, where $k_{1}<k_{2} <\dots<k_{n}$. For ...
59 views

### Proving a tighter upperbound (big-O) for this problem

Motivation So the other day I had fun providing a new solution to this famous question. In the analysis part I showed that my little algorithm has space complexity: ...
23 views

### what is the complexity of the below code? [duplicate]

I wanted to calculate the complexity of this pseudocode. In my knowledge, it is $n^2$ because the last loop only runs 8 times. I wrote a program to test it tends to run 8^logn (approximately). can you ...
30 views

### A problem about master theorem and recursion [duplicate]

Prove or disprove the following statement: If $f(n)\in \Omega(n^2)$ and $T(n) = 2T(n/2) + f(n)$ then $T(n) \in O(f(n))$. I think that the statement is false. Do you know any counterexamples?
42 views

### How is equation 1 simplified to equation 2 as shown below

In CLRS (Intro to algorithms) on page 362, it says eqn(1) : can be simplified to this equation(2): I would like to know how this simplification was arrived at. It shouldn't necessarily be a formal ...
29 views

### Does this LCS algo generate all the CS or only all the LCSs?

The Wikipedia article on LCS has an algorithm that backtracks all the LCS strings. This link redirects to the desired bulletin in the article. The C table in the backtrackAll function is pre-...
29 views

22 views

36 views

### How do I design a DP algorithm to count the minimum amount of continuous palindromic subsequences in sequence?

Taking a sequence, I am looking to calculate the minimum amount of continuous palindromic subsequences to build up such a sequence. I believe the best way is using a recursive DP algorithm. I am ...