Skip to main content

Questions tagged [recurrence-relation]

a definition of a sequence where later elements are expressed as a function of earlier elements.

Filter by
Sorted by
Tagged with
1 vote
1 answer
25 views

Recurrence Upper Bound Estimation

I'm going through CLRS and was trying to solve for the asymptotic bound of the following recurrence (exercise 4-5.4) $$T(n) = 4T(n/2) + n^2\text{lg }n$$ According to CLRS definition of Master Theorem, ...
Jackson Schuetzle's user avatar
0 votes
0 answers
21 views

Closed-form for exact number of iterations of binary search

Consider a sorted list of $n$ elements $x_1, \ldots, x_n$. Using binary search to find $x_k$ in this list takes $f(n, k)$ iterations, where $f : \mathbb{N}^2 \to \mathbb{N}$ is a function such that, ...
Electro's user avatar
  • 103
0 votes
0 answers
15 views

Asymptotic bound

How can this relation : $$ T(n)=4^n + 12 \cdot \sum^{n-2}_{i=1}{T(i)} $$ $$ T(1) = 1 $$ be evaluated to asysmtotic bound (Big O notation)? It could be easy if the upper bound of the sum were ...
User1342221's user avatar
1 vote
1 answer
74 views

Solving recurrence relation $T(n) = \max\{T(k)+T(n−k)+O(\min\{k, n-k\})\}$

My question arises out of this competitive programming problem. The idea is to find a unique element $u$ and then divide-and-conquer for the subarray to the left and to the right of $u$. Searching for ...
Elucidase's user avatar
0 votes
1 answer
91 views

Counting Towers Recurrence Verification From CSES Problem Set

Problem Statement: Your task is to build a tower whose width is 2 and height is n. You have an unlimited supply of blocks whose width and height are integers. For example, here are some possible ...
Ved K's user avatar
  • 1
-3 votes
1 answer
36 views

Closed form solution of T(n) = 5T(n−1) + n^2, to T(1) = 7

How to find the closed form solution of this equation? T(n) = 5T(n−1) + n^2, to T(1) = 7
Linx Silva's user avatar
0 votes
1 answer
29 views

Solutions to Recurences

I am currently learning various techniques in order to solve recurrences. One of which is the generalized master's theorem. The current problem I am attempting is as follows $H(n) < 4H(2n/5) + H(...
kusakus's user avatar
2 votes
1 answer
75 views

How to solve the recurrence $ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $ in terms of $\Theta$?

I'm attempting to solve the recurrence relation: $$ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $$ in terms of its asymptotic behavior ($\Theta$), specifically using the first case of the ...
Ferran Gonzalez's user avatar
1 vote
2 answers
58 views

How to Solve the Recurrence Relation $T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$ in terms of $\Theta$?

The provided recurrence relation is as follows: $$ T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2 $$ The goal is to express the solution in terms of the asymptotic notation $\Theta$. Unfortunately,...
Ferran Gonzalez's user avatar
0 votes
1 answer
135 views

what is the complexity of this sorting algorithm?

...
Arugo's user avatar
  • 59
1 vote
1 answer
39 views

Can you short-cut the substitution method for recurrence solving? (Wrong Guess but End Result Works)

The substitution method for recurrence solving wants you to come up with a guess function $g(n)$ which has the property $g(n) \in O(f(n))$. The goal is to show that your recurrence $T(n) \in O(f(n))$. ...
Yuirike's user avatar
  • 29
1 vote
0 answers
22 views

Is this a special case of a recurrence where the Master Method is not applicable?

So in an exam, this was the recurrence: $$ T(n) = 2T(n/2) + n log(n) -n + O(log(n))$$ $$T(1) = 1$$ Why does the master method not apply here? I think it is indeed int he form $$aT(n/b) + f(n)$$ You ...
Yuirike's user avatar
  • 29
1 vote
0 answers
31 views

Evaluating $T(n) = 4T(\frac{n}{5}) + \log n$: Master Theorem vs. Recursion Tree

I'm wondering where (how? why?) my reasoning (by imagining the recursion tree) deviates from the application of the Master Theorem (Case 1) to this recurrence. The Master Theorem gives $\Theta(n^{\...
Per48edjes's user avatar
3 votes
1 answer
354 views

Time complexity of tree algorithm

I'm new to recurrence relations and master theorem so trying to learn. Say there's an algorithm $A$ whose input is the root of a binary tree $T$. $A$ recurses so that it's called on each and every ...
onepiece's user avatar
  • 133
1 vote
2 answers
53 views

Solving recurrence by iteration, choosing base case

A question I am to answer wants me to find the big O of a recurrence, I am doing it with the iteration method. For the base case, which we get after applying the recurrence $i$ times, can we make this ...
user438409385's user avatar
1 vote
1 answer
109 views

Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)

Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element. Any subarray array[start, end] ...
patayala's user avatar
0 votes
2 answers
200 views

Solve the recurrence $T(n)=T(n-2)+\frac{1}{\lg{n}}$

Assume this recurrence: $$T(n)=T(n-2)+\frac{1}{\lg{n}}$$ I tried to draw its recurrence tree and I reached that the whole cost is $\dfrac{1}{\lg{n}}+\dfrac{1}{\lg{n-2}}+\dots+\dfrac{1}{x}$ that $x$ is ...
Mason Rashford's user avatar
0 votes
1 answer
63 views

Solve the recurrence $T(n)=T(n-1)+\frac{1}{n}$

Assume this recurrence: $$T(n)=T(n-1)+\frac{1}{n}$$ As we can use Master Theorem and Akra-Bazzi method here, I tried to draw a recurrence tree and I reached the whole cost of this tree is $\frac{1}{1}+...
Ferran Gonzalez's user avatar
0 votes
1 answer
36 views

Can this reccurrence recurrence be solved using Master Theorem?

Assume we have: $$T(n)=7T(\frac{n}{2})+n^2\lg{n}$$ Can we solve it using master theorem? As we know $n^{\lg_2{7}}\approx n^{2.81}$. On the other hand, we have $f(n)=n^2\lg n$. So we should compare $n^....
Ferran Gonzalez's user avatar
1 vote
1 answer
53 views

Solve a recurrence using Akra-Bazzi method where $p$ is not integer and integration is not easy

I recently faced this problem in CLRS ed.4 and couldn't find out how to attack it and solve it. Here's the recurrence: $$T(n)=3T(\frac{n}{3})+8T(\frac{n}{4})+\frac{n^2}{\log{n}}$$ Here's what I tried: ...
Mason Rashford's user avatar
1 vote
1 answer
62 views

Solving Recurrence Relations with induction

We got the following tasks in our Higher Algorithm class, to repeat our proof techniques from class: Find asymptotic upper bounds (as sharp as possible) for $T(n)$ in each of the following cases, ...
petrit.vidishiqi's user avatar
0 votes
1 answer
68 views

solve $T(n)=2T(\dfrac{n}{2})+\dfrac{8}{9}T(\dfrac{3n}{4})+\Theta(\dfrac{n^2}{\log{n}})$ using Akra-Bazzi method

Assume we have this recurrence: $$T(n)=2T(\dfrac{n}{2})+\dfrac{8}{9}T(\dfrac{3n}{4})+\Theta(\dfrac{n^2}{\log{n}})$$ We want to solve it using Akra-Bazzi method. As we know, $\sum_{i=1}^k\dfrac{a_i}{...
Mason Rashford's user avatar
3 votes
1 answer
99 views

On a table there are $N$ stacks. Stack $i$ contains $i$ tokens. Minimum number of moves to make all stacks empty

On a table there are $n$ stacks (numbered $1$ to $n$). Stack $i$ contains $i$ tokens ($1 \leq i \leq n$). During a move, a set of stacks can be chosen and the same number of chips can be drawn from ...
John's user avatar
  • 31
0 votes
1 answer
71 views

Struggling with Recurrence Relation using Telescoping Approach

I have the following recurrence relation that I am trying to solve using the telescoping approach: $T(n) = \begin{cases} T(\frac{n}{4})+ n^2 & \text{for } n \geq 4 \\ 1 & \text{otherwise} \...
Nancy Drake's user avatar
0 votes
2 answers
52 views

Prove $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(n\log^2{n})$ using induction

Please first take a brief look at my previous question. Here I want to do something similar but for $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})$. I know the answer is $T(n)=\Theta(n\log^2{n})$ and I want ...
Mason Rashford's user avatar
0 votes
1 answer
38 views

find $f(n)$ for recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})=\Theta(f(n))$

We have recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})$ and assume $T(1)$ is a constant. Find asymptotically tight bounds $\Theta(f(n))$ for $T(n)$. There's something that confuses me. We ...
Mason Rashford's user avatar
0 votes
1 answer
64 views

Find time complexity of $T(n)=3T(n-2)+O(n)$

I try to find the time complexity of following recurrence relation: $$T(n) = 3T(n-2) + O(n)$$ After subtitution,I get: $$T(n)=3^{\frac{n}{2}}T(0)+\sum_{i=0}^{\frac{n}{2}-1}3^iO(n-2i)$$ I wonder if the ...
Ash丶Dr's user avatar
1 vote
2 answers
185 views

Prove $T(n)=10T(\frac{n}{3})+n\sqrt{n}=\Theta(n^{\lg_3{10}})$ using induction

We have this recurrence: $$T(n)=10T(\frac{n}{3})+n\sqrt{n}.$$ We can solve it using Master Theorem and say it is $\Theta(n^{\log_3{10}})$. I want to prove it using induction but I don't know the ...
Mason Rashford's user avatar
0 votes
1 answer
74 views

Is my mathematical representation of search in binary search tree correct?

You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node's value equals <...
ilovewt's user avatar
  • 113
-1 votes
1 answer
47 views

Solve Recurrence Equation: 𝑇(𝑛)=𝑇(𝑛−4)+𝑛^2

I'm trying to practice recurrence equations, so I'm trying to solve this typology by unfolding method. I was wondering if what I write below was correct and obviously the result: $T(n) = n^2 + T(n-4) =...
emacos's user avatar
  • 121
0 votes
1 answer
118 views

Substitution method for the upper bound of a recurrence without an explicit base case

Pages 90-91 of 'Introduction to Algorithms' (4th ed.) show how the substitution method can be used for determining the upper bound on the recurrence: $$T(n) = 2T(\lfloor n/2 \rfloor) + \Theta(n) \tag{...
user51462's user avatar
  • 123
2 votes
2 answers
106 views

Justification for the properties of algorithmic recurrences in 'Introduction to Algorithms' (CLRS, 4e)

The fourth edition of 'Introduction to Algorithms' defines algorithmic recurrences on page 77 as follows: **Algorithmic recurrences [...] A recurrence is algorithmic, if for every sufficiently large ...
user51462's user avatar
  • 123
0 votes
2 answers
72 views

Clarification of divide-and-conquer recurrence explanation in 'Introduction to Algorithms' (CLRS)

The following excerpt is from page 39 of the 4th edition of 'Introduction to Algorithms' (emphasis added): 2.3.2 Analyzing divide-and-conquer algorithms [...] A recurrence for the running time of a ...
user51462's user avatar
  • 123
0 votes
0 answers
92 views

The master theorem soution to T(n) : T(n/4) + logn

When i tried to find the time complexity of this recurrence relation with the master theorem, I got log^2n, but I'm told that it's logn. I used the masters theorem, for this case.. a=b^k (1=4^0) ... ...
Yor's user avatar
  • 1
0 votes
1 answer
100 views

Comparisons using Quicksort with the median as the pivot

Background Using a simplified Quicksort algorithm where the first element of the array is assigned as the pivot we get the following pseudocode for the algorithm: Quicksort($a$): (1) If length($a$) $...
FD_bfa's user avatar
  • 103
0 votes
1 answer
88 views

How to derive time complexity of the Recurrence Relation - T(n,m) = T(n-1,m) + T(n,m-1) + c

I know that, T(n,m) = T(n-1,m) + T(n,m-1) + c it's the recurrence equation of Longest Common Subsequence algorithm. And the time complexity of the LCS in case of recursive method is O(2^n+m). The base ...
Samiddha 's user avatar
0 votes
1 answer
92 views

What recurrence describes the time complexity of this algorithm?

The problem is as follows: The input is an array $A$ of $n$ natural numbers such that: (1) if the maximum occurs in $A[p]$ for an index $p$, then $$A[1] \leq \ldots \leq A[p-1] \leq A[p]$$ and $$A[p] ...
Lucas Peres's user avatar
0 votes
0 answers
32 views

Does a bijective function exists behind every recurrence relation?

Consider these 2 questions where recurrence relations can be applied: Q1) Given an (nxm) where n denotes rows and m denotes columns of a grid, find the number of unique paths ($a_{n,m}$) that goes ...
rustlecho's user avatar
0 votes
5 answers
191 views

Find the asymptotic bound for the recurrence relation: $T(n) = T(\sqrt{n}) + 5n$

I've tried to expand the recursion: $$T(n) = T(n^{\frac{1}{2}}) + 5n = T(n^{\frac{1}{4}}) + 5(n^{\frac{1}{2}} + n) = T(n^{\frac{1}{8}}) + 5(n^{\frac{1}{4}} + n^{\frac{1}{2}} + n)$$ We have a total of $...
Yoxbox's user avatar
  • 5
2 votes
0 answers
118 views

Recurrence Relation for Longest Increasing Subsequence Problem

I am trying to solve the Longest Increasing Subsequence(LIS) Problem using different OPT Function than the one which normally used. I have been given this question as an extra credit and I have been ...
Sabe's user avatar
  • 21
0 votes
3 answers
120 views

How do I solve this recurrence equation?

I have to express the solution of the recurrence equation T(n) = T(an) + n where a is a constant, 0 < a < 1, in terms of θ using the iteration method. I am unsure of how I calculate the cost of ...
afahey03's user avatar
0 votes
1 answer
41 views

A Problem with Solving a Recurrence relation

I Hope someone Can help me with that: $T(1)=2$ $T(n)=\left(T(\frac{n}{2})\right)^2\cdot2^n $ what is the runtime complexity of the algorithm (base 2) Thanks a Lot!
Bubi's user avatar
  • 1
-2 votes
1 answer
46 views

Solving a recurrence relation formula with squared

I hope someone can help me with that: $$T(n)=T(2^{\sqrt{\log n}})+1$$ I will be asked to answer what is the runtime complexity of the algorithm. I tried to set m=2^ and still failed.
Bubi's user avatar
  • 1
0 votes
2 answers
61 views

Dropping terms in proving the runtime for a recurrence?

I am trying to learn how to prove the runtime of a recurrence relation, particularly through induction. I was looking at this lecture PDF, and on the first page, the author writes this: Recurrence: $...
gorilla_glue's user avatar
0 votes
1 answer
53 views

Algorithm Asymptotic Analysis

I'm trying to solve this time complexity: $T(n) = 2T(n-2) + n$, but having some challenges addressing the $(-2)$ component. Any insights on this complexity? Ended up with a section $[2^2\cdot1 + 2^3\...
cch's user avatar
  • 1
0 votes
3 answers
161 views

How to write recursive function in pseudocode for this number $a_n=n!+2^n$

I need to write recursive function in pseudocode for n-th number term of $a_n=n!+2^n$. Whole code should be contained in one function with $n$ as function argument.
DScounterGO's user avatar
-4 votes
1 answer
53 views

How to solve this recurrence relation: T(n) = R(n-1) + n log n R(n) = T(n-1) + n^2

How to solve this recurrence relation: T(n) = R(n-1) + n log n R(n) = T(n-1) + n^2
Aziz's user avatar
  • 1
4 votes
2 answers
1k views

Does T(n) = 2 · T(2n) + n apply to Master method?

I'm trying to apply the master method to the following recurrence: $$T(n) = 2 \cdot T(2n)+n.$$ We have $a=2$ and $b=1/2$. Also, $f(n)=n$ and $n^{\log_b a} = n^{\log_{1/2} 2} = n^{-1}$ since $\log_{1/2}...
Jarvis's user avatar
  • 109
-1 votes
1 answer
93 views

Modified Quickselect - Proving linear time

As we know, Quickselect chooses a 'random' element in order to partition the array around that element in every iteration. Assume the random element is at most the $\frac{1}{k}\cdot n$ largest element,...
Aishgadol's user avatar
  • 355
-1 votes
2 answers
2k views

T(n) = 2T(n/4) + sqrt(n)

T(n) = 2T(n/4) + sqrt(n) I am trying to solve this question and ended up with the answer O(√n.log√n). But when I checked online the answer was supposed to be O(√n.logn) or √n.logn base 4. I am not ...
Crack_on_life's user avatar

1
2 3 4 5
15