Questions tagged [recursive-algorithms]

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

Filter by
Sorted by
Tagged with
-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.

1
2 3 4 5
24