# Questions tagged [recursion]

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

456 questions
Filter by
Sorted by
Tagged with
19 views

### Solve recursive function $T(n) = T(n/3) + T(n/6) + n^{\sqrt{\log{n}}}$

in one of my college assignments i came up with the following recursive function which I'm asked to solve: $T(n) = T(n/3) + T(n/6) + n^{\sqrt{\log{n}}}$ I tried change of the variable or the recursion ...
24 views

### Solve the recursive function $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$

in one of my college assignments i came up with the following recursive function which I'm ask to solve: $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$ I could not use master method on it and it ...
23 views

### Is “backward substitution” and “backtracking” the same thing?

From my limited knowledge, they both are related to solving recurrence relation. Solving recurrence relation using backward substitution Solving recurrence relation using backtracking Can the terms ...
15 views

### Recurrence equation [duplicate]

What is the recurrence equation of this function and how to calculate it ...
53 views

### Using a special given machine find a recursive function that can sort A in linear time [duplicate]

in one of my assignments i came to this question with no additional info: Given a machine that can compute the kth smallest item of an Array ...
41 views

### What is the solve of F(n,n) = F(n-1,n) + F(n, n-1) + 1 Where F(0,a) = 1 and F(a, 0) = 1 for every a

I'm given the following python function: ...
22 views

### Time complexity of a recursive algorithm with two lists as parameters

The goal is to find the function T which describes the time complexity of an algorithm who merges two lists (but the lists are given inversely sorted). The problem is that recursive calls depend on an ...
14 views

### How do I work out the recurrence relation of the given function?

I am looking to find the recurrence relation (RR) of the fnA(), but I am unsure how $n$ is to be represented. (More specifically, I am trying to work out the ...
50 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: ...
27 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 ...
31 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?
47 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 ...
30 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-...
31 views