Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
1,154
questions
-1
votes
2answers
31 views
$T(n) = T(\frac{n}{2}) + n\log(n)$ [closed]
$T(n) = T(\frac{n}{2}) + n\log(n)$
please provide a solution to the given recurrence equation using substitution method.
0
votes
1answer
20 views
Prove using the definition of little o. [closed]
How I can prove that:
(100*(8^n)) ∈ o(9^n)
using the definition of little “o” ?
o : an asymptotic notation in data structure ...
-1
votes
1answer
29 views
Prove using the definition of θ. [closed]
How I can prove that:
$$
((n^2) − 3*n + 2) ∈ θ(n^2)
$$
using the definition of $θ$ ?
θ : an asymptotic notation in data structure algorithm.
0
votes
0answers
17 views
Algorithm for Box Selection / Space Optimization
So, I have an optimization/space management problem. This same question is posted on two SE sites simultaneously, Stack Overflow and Mathematics, since I think it is fitting for both.
Let's say I have ...
0
votes
1answer
21 views
Solving recurrence using characteristic equation
I am recently learning the how to use the various methods to solve recurrences. So far I have acquainted myself with the Master's Theorem and Substitution method. One method I just can't seem to ...
1
vote
1answer
34 views
Finding combinations of 81 discrete values that add up to a known value
First, I'm a mechanical engineer, and not a programmer. So for practical purposes, the answer may be as simple as "Excel can't do that without VB", or even "Excel can't do that". ...
2
votes
2answers
86 views
How to simplify the summation of a recurrence relation
After solving the recurrence relation
$$T(n) = 3T(\frac{n}{3}) + n\log(n)$$
I get following equation
$$T(n)=3kT(\frac{n}{3k})+ n\log(n) + n\log(\frac{n}{3}) + n\log(\frac{n}{3^2})+\dots+n\log(\frac{n}{...
0
votes
2answers
61 views
Simplest algorithm to cover a sphere
What is the simplest algorithm for covering the surface of a sphere by walking. To word it another way, what would be the simplest algorithm a person could take to walk the surface of the earth?
0
votes
1answer
28 views
Apply master theorem work for binary search with linear operation at each level
I'm working on the problem from the Introduction to Algorithms book, where there is the following recurrence relation $T(n) = T(\frac{n}{2}) + \Theta(N)$, where $N$ is the size of the array we are ...
6
votes
0answers
121 views
Robot moves from $(x,y)$ to $(x+y, y)$ or $(x,x+y)$
I was working on some coding related to this topic I found on Stack Overflow. This lead me to a math problem I thought would be interesting. I was wondering if one was given a starting point, what ...
1
vote
1answer
41 views
Recursive function with multiple recursive terms
I have a questions about recursive functions. What I usually find online are discrete functions where a new term is computed from the previous one starting from an initial condition.
What I'm ...
0
votes
0answers
8 views
How to solve a recurrence with characteristic eqn
T(n) = 2T(n/3) + 1, where T(1) = 0
Could someone tell me how I can solve this without using Master's Theorem?
I understand that for linear recurrences we can use the k degree linear recurrence ...
0
votes
0answers
22 views
Division Algorithm: Is slow division equation on Wiki correct?
The slow division algorithm on Wiki appears incorrect given my testing. Does anyone know if this recurrence is correct or works for their sample?:
$R_{j+1} = BR_j - q_{n-(j+1)}D$
where
$R_j$ is the $...
0
votes
2answers
33 views
Derivation of a recursive binomial coefficient algorithm
I am working through a Haskell book and I see that the binomial coefficients formula
$$\binom{n}{k} = \frac {n!}{k! (n - k)!}$$
is expressible as recurrence relationships
\begin{align}
\binom{n}{k} &...
1
vote
1answer
30 views
How Many Iterations for Recurrence Relation To Terminate?
I have the following recurrence, and I want to upper bound how long it takes to terminate.
$R(0) = n$
$R(t) = R(t-1) - \max\left(1, \left\lfloor\sqrt{R(t-1)}\right\rfloor\right)$
The recurrence stops ...
1
vote
2answers
64 views
Is it possible to calculate the input variable of a specific encryption function without brute-forcing it?
I didn't know where to post this question, here or SO but I feel it's more of a math problem.
Lately I have been reverse engineering a game, and figured out how it takes user input, encodes it, and ...
1
vote
1answer
46 views
Recursive inclusion exclusion principle
The inclusion exclusion principle is as follows:
$P\Bigl(\bigcup_{i=1}^n E_i\Bigr) = \sum_{i\le n} P(E_i) - \sum_{i_1<i_2}P(E_{i_1}\cap E_{i_2})+\sum_{i_1<i_2<i_3}P(E_{i_1}\cap E_{i_2}\cap E_{...
2
votes
1answer
51 views
Proof by induction - algorithm
I need some help to sort out if my answer is right for this question. The algorithm calculates $x^n$.
Question: Argue the correctness of the algorithm using proof by induction.
Note: Even if you haven'...
0
votes
1answer
21 views
Algorithmic complexity of iterative - recursive solution
I had an exam of algorithms and data structures today and I was given an excercise I wasn't prepared for. The excercise was some pseudocode that we needed to extrapolate the time complexity out of.
...
1
vote
0answers
20 views
Recursive function inside loop analysis using recursive techniques
The question wants me to analysis the performance of the code using recursive techniques.
I am still new to analysis of algorithms. I know how to analyze loops and recursion separately but, in this ...
1
vote
0answers
26 views
Applications of Products of Random Matrices
I'm studying the paper "Matrix concentration for products" and I'm trying to find simple applications of the inequalities for the expected value of the spectral norm of products of random ...
0
votes
1answer
17 views
exponential equation quick-select algorithm
i'm trying to proof that quickSelect algorithm RunTime complexity is: Theta(n)
With Akra-Buzzi method.
So i need to Solve this recursive function: T(n) = T(n/5) + T(7n/10) + n
i need to find p, such ...
1
vote
1answer
48 views
Help define this recursive sequence iteratively
(Note you do not need to have seen the original olympiad problem to answer my question)
I was attempting the fifth problem from the 2008 Canadian Mathematical Olympiad, and got all the way to this ...
0
votes
2answers
46 views
$T(n)=T(\frac{n}{3})+T(\frac{2n}{3})+cn$
I'm trying to understand the following proof from 'Introduction to Algorithms' that the recurrence $T(n)=T(n/3)+T(2n/3)+cn$ has solution $O(n lg n)$.
I'm stuck on the fourth step when he replaces $-d(...
1
vote
0answers
26 views
Finding the recursive definition of following:
I am struggling with finding a recursive definition of the following:
$$a_0 = 1$$
$$a_1 = -(nx-1)$$
$$a_2 = (n+1)*x*(nx-2)+1$$
$$a_3 = -((n+2)*x*((n+1)*x*(nx-3)+3)-1)$$
$$a_4 = ((n+3)*x*((n+2)*x*((n+1)...
1
vote
0answers
21 views
Finding a function that satisfies an integral relationship
I want to find a set of functions (if they exist) $ g_{l}(x)$ that are recursively defined as $$g_{l-1}=-(l+1)\rho'g_{l}$$
and satisfy the following integral equation up to index $l=k$:
$$ 0 = \int_{-\...
0
votes
0answers
36 views
Solve the recurrence equation T(n)=2T(n/16)+sqrt(n)
$$
T(n)=2T(\frac{n}{16})+\sqrt{n}
$$
I used Master Theorem and I found that it should be T(n)= Θ(√n). Is it correct?
0
votes
0answers
22 views
Runtime Complexity of Memoization
I am struggling to analyze the runtime complexity of the following algorithm formally:
Given a string s and a dictionary of words dict(wordDict), add spaces in s to
construct a sentence where each ...
0
votes
1answer
21 views
Search a word in a matrix runtime comlexity
Trying to analyze the runtime complexity of the following algorithm:
Problem: We have an $m \cdot n$ array $A$ consisting of lower case letters and a target string $s$. The goal is to examine whether ...
0
votes
0answers
36 views
Master Theorem $T(n)=4T(n/4)+ 5n(\log n)^2 +n\sqrt n$
What will be the value of $k$ and $p$ in this case, does master theorem really apply here?
then what will be final time complexity for this case?
this was in my analysis and design of algorithms exam.
2
votes
1answer
55 views
Closed form for continued fraction
I am working with a recursive algorithm and I have realized that in each step it computes something equivalent to:
$A_{0}=\frac{a}{b}$
$A_{1}=a/(b-\frac{a^{2}}{b})$
$A_{2}=a/(b-\frac{a^{2}}{b-\frac{a^{...
4
votes
1answer
80 views
Brick wall with maximum height 3
Given n same-sized rectangular bricks. We want to build a wall with these constraints:
All bricks should be horizontal.
We can put a brick on two other bricks, such that the middle of the top brick ...
0
votes
1answer
18 views
Inferring a recurrence relation, stairway climbing
Problem. Suppose a dog can jump one or two steps of a stairway of $k$ steps. How many different ways can this dog climb up? Answer it with a recurrence relation.
Solution. I calculated the number ...
-1
votes
1answer
42 views
How can one prove the worst case scenario of an algorithm purely mathematically?
How can someone prove purely mathematically that the worst case scenario (Big O) of the number of iteration of a recursive search algorithm is, let's say, 2 * log3(n)?
The only method that comes in my ...
0
votes
0answers
20 views
In this Case how to check the Master Theorem?
𝑇 (𝑛) = 8 ⋅ 𝑇 (𝑛/2) + 𝑛 + 𝑙𝑜𝑔 𝑛 ?
a = 8 ; b= 2 log2 (3) =3
f(n) = n + log n
How to check the Master Theorem ?
Should I go through every single case ?
0
votes
2answers
38 views
Recursively generating all partitions
Given a set $\{1,2,\ldots,n\}$, I would like to recursively generate all partition of size $r$ and $n-r$. For instance, we start with the partitions
$$\{1,2,\ldots, r\} \quad \{r+1,\ldots, n\}$$
and ...
1
vote
0answers
68 views
Dynamic Programming question - n floors and m boxes
Q: Given a building with $n$ floors, each floor $i$ has $c_i$ boxes in it. You need to find a way to store all the boxes in at most $m$ floors. Moving boxes from one floor to another is allowed only ...
1
vote
1answer
24 views
Optimal allocation between loans
I have a two part problem. The first asks whether I can optimally determine how I should split my weekly paycheck towards two loan payments to ensure the shortest total time to payoff my loans. The ...
1
vote
2answers
97 views
Orthogonality of Legendre polynomials using specific properties
I'm having significant issues with a problem and would appreciate any help at all with it. It is regarding proving the orthogonality of Legendre polynomials using a specific recursion formula and ...
0
votes
1answer
61 views
Tips for a recursive function, proof by induction
Suppose the following
$$ f(0)= 0$$
$$ f(1)=2$$
$$ f(n)= 4f(n-1)-3f(n-2)$$
I want to prove that
$$f(n)= 3^n -1$$
by induction.
I started by trying this
$$f(n+1)=4f(n)-3f(n-1)$$
Which gives me this:
$$ ...
1
vote
1answer
43 views
Solving this nonlinear system (a localization problem) with gradient descent.
I have the following algorithm designed to find the global minimum of the simple function $y=(x+5)^2$.
...
0
votes
1answer
63 views
How to solve this linear recurrence relation
how to solve following recurrence relation :
$f(n) = 3 * f(n - 1) + 4$
i've got that recurrence relation from following sequence, where f(n) is nth value of the following sequence.
$7, 25, 79, 241, ...
0
votes
0answers
20 views
Sum of squared error in higher dimensions
I wrote an approximation search algorithm for solving a localization problem in 2D space. That is, given the coordinates of three observers, the velocity of some signal, and the time at which each ...
1
vote
1answer
16 views
Why can $T(x,c)=\theta(x),T(c,y)=\theta(y),T(x,y)=\theta(x+y)+T(x/2,y/2)$ be rewritten as $T(x,y)=c(x+y)+T(x/2,y/2)$
I'm doing a self study on MIT Opencourseware Algorithms course and the first problem set can be found here: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-...
1
vote
0answers
32 views
Recursive Definitions for Theorems
I recently encountered with the statement "Recursive definition may be used to define not only sets but also to prove correctness of functions." and questioned on whether it is really true. ...
0
votes
0answers
24 views
How to find the equations for a, b, c, d of the Master Theorem?
$$T(n)=a \cdot T\left(\frac{n}{b}\right)+\Theta\left(n^{c} \cdot \log ^{d} n\right)$$
Now I want to find equations for a,b,c,d
So a = ....
What I have tried to far is this:
$$T(n)=a \cdot T\left(\frac{...
0
votes
1answer
39 views
The answer of a recursive equation: $T(n) = T(n /\log(n)) + 1$
How to solve:
$$T(n) = T(n / \log(n)) + 1$$
I tried the recursive solution to reach $T(1)$, but I failed. The reason was that I could not find out after how many recursion I would reach $T(1)$.
0
votes
0answers
12 views
How to update a sample covariance matrix with a weighted average?
I would like to update a covariance matrix $\mathbf{R}_T$ with a new incoming sample at time $T+1$, i.e. I would like a rank-1 update of the form $\frac{1}{T+1} [T \mathbf{R}_T + \mathbf{x}_{T+1}\...
1
vote
1answer
43 views
A computably enumerable set $m$-reduces to the halting problem
I'm trying to show that if $A$ is c.e., then $A\leq_m K$, where $K$ is the set of all programs that halt on themselves.
I'm trying to use essentially the same strategy as I described here.
$A$ is c.e.,...
0
votes
2answers
49 views
Can somebody help me with this mathematical induction proof? [closed]
It's a recursive equation and I'm not sure how to demonstrate it through mathematical induction.
