# Questions tagged [recurrence-relation]

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

736 questions
Filter by
Sorted by
Tagged with
1 vote
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, ...
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, ...
• 103
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 ...
1 vote
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 ...
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 ...
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
29 views

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 ...
• 133
1 vote
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 ...
1 vote
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] ...
• 11
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 ...
63 views

1 vote
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: ...
1 vote
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, ...
68 views

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 ...
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 ...
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 ...
1 vote
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 ...
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 <...
• 113
47 views

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 ...
• 21
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 ...
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!
• 1
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.
• 1
61 views

• 1
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.
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
• 1