Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [recursive-algorithms]

Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.

6
votes
4answers
107 views

Computing how many distinct digital products are below $10^n$

Given a number $n$, its digital product is the product of its digit. So the digital product of $15$ is $1\times 5=5$, and the digital product of $760$ is $0$, etc. I recently saw a nice video on ...
0
votes
1answer
28 views

A specific and interesting recurrence relation

Let f and g be increasing functions such that the sets {f(1),f(2),...} and {g(1),g(2),...} partition the positive integers. Suppose that f and g are related by the condition g(n)=f(f(n))+1 for all $n&...
-1
votes
3answers
27 views

Explicit form of $ b_1= 2, b_k = b_{k-1} + 2\cdot 3^k$ for all integers $ k\ge 2 $ [closed]

As the title says, I need to find the explicit form of the recursive sequence defined above, and I am very stuck on this.
1
vote
3answers
40 views

Summation formula for this?

I have found the following summation formula based on a recurrence. It supposes $n = 2^k$ where k is an integer. I've intuitively discovered that the following closed form may be true (following the ...
0
votes
1answer
33 views

How many unlucky numbers in segment $[a;b]$

Some numbers are called unlucky if their decimal representation contain number $5$. For example: $123456,245,1555$ are unlucky numbers and $111,123,147$ are not unlucky numbers. In how many unlucky ...
0
votes
0answers
25 views

finding the recursive function for given code

Hey guys, can you give me some guidelines on how to get through questions like this, and help get the closed formula T(n) of the function?
0
votes
1answer
17 views

Heapsort using MaxHeap and MinHeap

As I read in Introduction To Algorithms [3rd edition]: MaxHeap is used to sort an array into ascending order, while MinHeap is used to sort an array into descending order. And the tree below can be ...
0
votes
1answer
10 views

Recursive Algorithms - Number of Comparisons - Time Complexity Functions

My text is not exactly straightforward in this section and I'm struggling to figure out how to do this problem: There isn't anything in the book which explains how to find the number of comparisons ...
0
votes
1answer
22 views

Time Complexity of CLRS Optimal Parenthesis Algorithm

I am reading the Introduction to Algorithms CLRS book, and I am unsure about the time complexity of one of the algorithms that is a recursive algorithm that calls itself twice. This chain matrix ...
0
votes
0answers
27 views

Partition problem where partition are in increasing order.

For given $n$ and $S$, how many possible combinations are there such that: $x_1 + x_2 + .. + x_n = S $ $\forall i, x_i \leq x_{i+1}$ $\&$ $x_i \geq 1$ For example, if $n$ = 3 and $S$ = 5, there ...
1
vote
0answers
14 views

Intro to Metamathematics Kleene $\S54$ Lemma IId

In this section, Kleene builds a formal system for primitive recursive functions. The beginning of the proof for lemma IId is skipped because it comes for general properties, but I must be missing ...
0
votes
0answers
32 views

Hull-Dobell theorem for linear congruential algorithm

Hull-Dobell theorem says for $x_{n+1}= ax_{n}+c \, mod\, m$ if c ≠ 0, correctly chosen parameters allow a period equal to m, for all seed values. This will occur if and only if c and m are relatively ...
-1
votes
0answers
16 views

Longest increasing subarray with a recursive function

Input : 1, 9, 2, 7, 20, 13, 50 Output : 2, 7, 20 So far, I got a iterative function. ...
0
votes
0answers
11 views

Extension of the Clenshaw Recurrence Formula

I am wondering if the Clenshaw Recurrence Formula Link, which is used to evaluate a sum $$f(x)=\sum_{k=0}^N c_k\,F_k(x)$$ when $F_k(x)$ obeys the recurrence relation $$F_{n+1}(x)=\alpha(n,x)\,F_{n}(...
0
votes
1answer
39 views

Calculate the running time of the code snippet below

for (i=2*n; i>=1; i=i-1) for (j=1; j<=i; j=j+1) for (k=1; k<=j; k=k*3) print(“hello”) I sopused that its N^5 but Im not sure
1
vote
0answers
10 views

Question about Proof: Semi-decidable => Recursively Enumerable

Def. A set A is recursively enumerable if $A = \emptyset$ or if there exists a total computable function $g$ such that $A = R(g)= \{z | \exists x. g(x) = z \}$. Def. A set A is semi-decidable if ...
-1
votes
0answers
117 views

Algorithm to allow player 1 to force a win

Two players play a game, starting with three piles of $n$ pebbles each. Players alternate turns. On each turn, a player may do one of the following: take one pebble from any pile take two pebbles ...
0
votes
0answers
44 views

Closed form of generalized Josephus problem

I have to solve Josephus problem where every 5th man gets killed and I have to find out the living person number and $n = 10000$ The generalized solution of Josephus problem is $J(n,k) = ((J(n-1,...
0
votes
0answers
7 views

Finding Volatility of multiple numbers

I have set of few numbers like below ranging from -9 to 9 , If set of numbers has more difference to each other than volatility should be very high , if all numbers has very short difference , ...
2
votes
2answers
42 views

Does this recursive function have a function in terms of n?

I am trying to convert the following recursive function to a non-recursive equation: $$f(2) = 2$$ For $n>2$: $$f(n)=nf(n-1)+n$$ I have calculated the results for n=2 through to n=9: $$\begin{...
0
votes
1answer
27 views

How to solve equations using big $\Theta$

How would I prove that the statement $$10n^3 +3n = \Theta(n^3)$$ is true/false?
1
vote
1answer
32 views

Using the Master Theorem to solve a recurrence

I have the following recurrence relation, which I am trying to solve using the Master Theorem: $$ T(n) = 2T(n/2) + n^{\frac 12} + \log n $$ Comparing the above recurrence to the recurrence of the form:...
0
votes
0answers
29 views

Solving a recurrence using the Master Theorem

I have the following recurrence relation, which I'm trying to solve using the Master Theorem: T(n) = 2T(n/2) + n(2 + sin(n)) I compared this recurrence to the one of the following form: T(n) = aT(n/...
0
votes
1answer
51 views

how to work out a computer program running time

I have a question and im not sure how to tackle it.... algorithms have running times proportional to the following functions of the input size, denoted N: $N^2$ $2^N$ In one minute of computing ...
-1
votes
1answer
19 views

Algorithm to solve systems of first order “triangular” linear difference equations

I have a system of first order linear difference equations, which look like this: \begin{align*} \vec{x_n} = A \vec{x_{n-1}} + \vec{b} \end{align*} Where $A$ is an upper triangular matrix. What ...
3
votes
0answers
48 views

Solving recurrences using substitution method

I have given $$ T(n)= \begin{cases} T(n/3)+T(2n/3)+n,\quad &n>1 \\ 1, \quad &n=1 \end{cases} $$ I tried it again and again but couldn't think beyond, $$ T(n)=T(n/27)+3T(...
1
vote
0answers
24 views

How to prove that a recursive function with inner summation is approximately equal to some closed-form equation?

The following problem is taken from an algorithms textbook(specifically, in the context of complexity analysis of recursive algorithms.) Starting from the equation: $$nf(n) = n(n-1) + 2 \sum_{k=1}...
1
vote
2answers
73 views

Leaving recurrence summation in terms of $k$, $\sum_{i=0}^{k-1}\frac{3^i\sqrt{\frac n{3^i}}}{\log\frac n{3^i}}$

I have an exercise where I need to use the substitution method to solve the following recurrence and determine their corresponding complexity. $$t(n)=3t(n/3) + \frac{\sqrt n}{\log n}$$ After some ...
0
votes
1answer
18 views

Find $F_{2^n}$ for polynomial time.

You have the nonnegative integers $a_1, a_2, ..., a_k, F_1, F_2, ...,F_k$. Consider the sequence $F_n = a_1F_{n - 1} + a_2F_{n - 2} + ... + a_kF_{n - k}, \forall n > k$. Suggest a polynomial ...
0
votes
1answer
25 views

Fractional Knapsack Problem Linear Time

So I came across a solution to the fractional knapsack problem in linear time here: http://algo2.iti.kit.edu/sanders/courses/algdat03/sol12.pdf I'm not sure I understand the algorithm given. We ...
0
votes
1answer
30 views

Understanding the Master Theorem - Determining the levels of recursion

I am trying to understand the proof for the Master Theorem. I have started by unwinding the following recurrence in order to find the total running time of an algorithm whose time complexity can be ...
1
vote
0answers
15 views

Divided Differences expanded form definition.

From definition of divided differences we have that $$f[x_0,\cdots,x_n]=\sum_{j=0}^n\frac{f(x_j)}{\Pi_{{k\in\{0,\cdots,n\}-\{j\}}}(x_j-x_k)} $$ It makes completely sense to have $k\neq j$ otherwise ...
2
votes
1answer
35 views

Optimal permutation for differential storage

This is a practical problem I encountered recently. I'm convinced that it has been solved before, however I don't know where to start looking as I'm unfamiliar with all the terminology involved. Hope ...
2
votes
2answers
110 views

is there a faster method to calculate $1/x$ ($x$ an integer) than this?

I gave this stackexchange a second go. Is there a faster way to calculate $1/x$ than the following: Calculate $100/x$ (.or other arbitrary positive power of $10$) with remainder Write multiplier in ...
1
vote
1answer
21 views

Mathematical Induction for a defined Fibonacci Function

I'm a bit stuck on this problem and can't figure out how to proceed. We have the following Fib. recurrence given to us: $f(0;a,b) = a;$ $f(1;a,b) = b;$ $f(n;a,b)=f(n-1;b, a+b)$ The problem defines ...
2
votes
0answers
42 views

How to determine how fast something is going towards infinity?

Just for a little bit of information I'm more of a programmer and less a mathematician so if some of my terms seem out of place it is due to a lack for formal training in Math. While working on my ...
0
votes
0answers
69 views

Longest Increasing Subsequence Using Divide-And-Conquer

I'm required to solve the LIS problem using Divide-and-Conquer. The hint provided is the following: For each position in the array find the cardinality of the longest sequence that ends up with it, ...
0
votes
2answers
34 views

Sinusoidal Generation in Recursive Algorithm

I need to generate sinusoidal values for varying frequencies. I'm making a DTMF tone generator but I must generate my own values of sine using recursive algorithms. The exact wording of how I'm ...
0
votes
3answers
78 views

Solving a recurrence relation: can't figure out how to convert from summation

I am really struggling to solve this recurrence. $$ T(n) = T(\sqrt{n}) + n. $$ I am asked to give asymptotic upper and lower bounds for $T(n)$. I am free to use any method to arrive at my answer, ...
1
vote
1answer
28 views

$(G,\cdot)$ and $M \subseteq G$. Prove that the following algorithm computes the subgroup generated by M.

Let $(G,\cdot)$ be a finite group and $M \subseteq G$, $M\ne \emptyset$. Prove that the following algorithm computes the subgroup generated by M : $$S_{0}:=\{{e}\} , H_{0}:=\{{e}\}\\ S_{n+1}:=(S_{n}\...
0
votes
0answers
36 views

How can I compute recursive QR-factorization?

I wonder if it's possible to find the $Q$ and $R$ matrices from this QR-equation with only compute QR at one time only: $$A = QR$$ if, the first column of $A$ got removed and then a new column got ...
1
vote
1answer
221 views

Variance of parameter estimate using recursive least squares

I am learning about recursive least squares estimation using a forgetting factor $\lambda$ as a tool for treating time variations of model parameters and have become stuck on the following problem. ...
-1
votes
1answer
27 views

show algorithm to compute square root converge. [closed]

Consider the calculating the square root as follow: Let's say we want to compute square root of $x>0$, pick a number $g_1>0$, then if $|g_1^2-x| < 0.00001$ then done. Else, let $g_2=\frac{g+\...
-1
votes
2answers
119 views

Solve the operations needed for the recursive formula

$f(n) = 1+\frac{1}{n}\sum_{i = 0}^{n - 1} f(i)$ Base case: $f(0) = 0$ how can I solve the recurrence?
0
votes
3answers
38 views

sequence that adds its previous results

Let $x = 0.3$. The first number of the sequence is $x$. The second number is the first number + $(0.3\cdot 0.3)$. The third number is the second number + $(0.3\cdot 0.3\cdot 0.3)$. This is a ...
0
votes
0answers
22 views

Is there a specific search paradigm for finding pairs in a set?

I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of ...
0
votes
2answers
30 views

What is a goal of Galileo's magnetometer recursive filter

I'm designing the basics of space magnetometer instrument for academic project and I came across a Galileo mission investigation document, with data flow described in chapter 6. As a first ...
1
vote
2answers
49 views

proof that Ackermannfunction is uniquely defined and finding algorithm without recursions to calculate its values

my question is involving the Ackermannfunction. Let's call a function $a: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ "Ackermannfunktion", if for all $x,y \in \mathbb{N}$ the following ...
0
votes
1answer
36 views

How to prove that class of “recursive” and “recursively enumerable” languages are not equal?

I would like to formulate a formal proof for showing that the classes of recursive and recursively enumerable languages are not equal. I know that recursive languages are accepted by Turing machines ...
0
votes
1answer
36 views

Recurrence proof by induction

I'm having a hard time to understand how am i supposed to solve this question: $T(n) = \sqrt{n}T(\sqrt{n})+n$. Prove by induction that $T(n) = \Theta (n \log{(\log{(n)})})$. These are all the data ...