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

learn more… | top users | synonyms

0
votes
0answers
25 views

Proving a dynamic programming recurrence for coin exchange correct

Suppose I have n kinds of coins c_1, c_2, ..., c_n. I'm I given: S, sum of money I should construct with minimum number of coins. I came into the following formula: T(n,S) = T(n-1,S) if c_n > S ...
-3
votes
1answer
22 views

time complexity analysis of recurrence relation [duplicate]

I am not able to solve time complexity analysis of this recurrence relation: T(n)=3T(n/2)+n^2.I want to find time complexity analysis of this recurrence relation without using masters theorem could ...
3
votes
1answer
33 views

About a step in the analysis of Quicksort by Sedgewick and Wayne [duplicate]

In the book Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, when they are analyzing quicksort (page 294), they present the sequence of transformations: $$\begin{gather*} C_N = N + 1 + ...
1
vote
1answer
80 views

Solving a bivariate recurrence equation

I'm dealing with this recurrence equation: $\qquad\displaystyle T(m, n) = T(m/2, n/2) + T(m, n/2) + O(1)$. Any idea how to solve this? I've looked in to few advanced resources but the literature on ...
3
votes
2answers
85 views

Closed form for the recurrence T(n) = T(n-1) + n²

Given the following recurrence: $$ T(n) = T(n-1) + n^2$$ How can I prove it to be $O(n^3)$ with the substitution method? The $O(n^3)$ guess derives from the fact that at every step of the recursion ...
1
vote
0answers
25 views

how to solve recurrence T(n) = 2T(n/2)+n using substitution method [duplicate]

The required solution is given. I have to prove that its solution is $O(n\log n)$. My idea is shown below: I have to prove, $T(n) \le cn\log n$ for some constant $c$ $$\begin{align} T(n) &\le ...
0
votes
1answer
35 views

Complexity calculation using a recurrence relation [duplicate]

I just can't solve this problem, I'm new to reccurences. I have this recurrence $T(n)=n*T(n-1)$ $T(1)=1$ The second term will be: $T(n-1)=(n-1)*T(n-2)$ And so on. It's complexity is O(n!) but i ...
2
votes
1answer
29 views

Recurrence relation complexity [duplicate]

I just learned about recurrences and I just can't solve this problem. I have this recurrence relation: $$ T(n) = \begin{cases} k\cdot T(\frac{n}{k}) & n > 0\\ 1 & n = 0\\ \end{cases} $$ ...
1
vote
1answer
149 views

How to solve T(n) = T(n-1) + n^2?

See title. I'm trying to apply the method from this question: http://stackoverflow.com/questions/13674719/easy-solve-tn-tn-1n-by-iteration-method. What I have so far is this, but I don't know how to ...
4
votes
1answer
51 views

Cases of Master Theorem

Suppose that we have $ \\ T(n)=\left\{\begin{matrix} c, & \ \text{if } n<d\\ aT\left( \frac{n}{b} \right )+f(n), & \ \ \text{if } n \geq d \end{matrix}\right.$ The Master theorem is the ...
0
votes
0answers
18 views

Solving $T(n)=2T(n/2) + n \lg n$ , For ex: Counting inversions implemented with full mergesort [duplicate]

How to solve the recurrence equation $T(n)=2T(n/2) + n \lg n$ For ex: I implemented "Counting inversions" with a full mergesort instead of just using merge part, So the outer complexity will be $n ...
1
vote
0answers
43 views

Number of ways to connect sets of $k$ vertices in a perfect $n$ -gon [closed]

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial ...
0
votes
2answers
226 views

Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes?

http://www.algorithmist.com/index.php/UVa_10918 The above link is a solution to UVa 10918 Problem. The problem is based on Dynamic Programming. I am not able to understand this approach to the ...
0
votes
0answers
17 views

Master Theorem applied to recurrence relations [duplicate]

Can anyone explain how to use the master theorem to the following problem... $$T(n) = T(\frac{n}{3}) + \log(n)$$
1
vote
1answer
45 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and ...
0
votes
1answer
73 views

T(n/3) + log(n)

how do you find the Theta of this problem... $$T(n) = T(\frac{n}{3}) + \log_2(n)$$ I end up getting a pattern of $$T(\frac{n}{3^{k}}) + \log_2(\frac{n}{3^{k-1}}) + \log_2(\frac{n}{3^{k-2}}) + ... + ...
1
vote
1answer
31 views

Recurrence relation chip and conquer

Can anyone explain how to find the $\Theta()$ of this equation... $$T(n) = 3T(n-4) + cn$$ When I solve this problem I get this using the $k$ -th iteration... $$T(n) = 3^{k}T(n-4k) + 3^{k-1}c(n-2(k-1)) ...
2
votes
0answers
20 views

Asymptotic of interesting recurrence relation [duplicate]

I want to study the asymptotic behavior of the following recurrence relation: $y_1=1$; $y_{n+1}=y_{n}+(1+\frac{y_n}{n})^{-n}\ \ $ for $n\ge 1$. I made an initial attempt and guessed that $y_{n} ...
0
votes
0answers
13 views

runtime-analysis, runtime of this equation [duplicate]

Recurrence relation How can I determine the theta of this equation ? T(n)=3T(n/3)+3^(n/3) ,T(i) = 0 if i <0 My teacher gave me this clue : 2<=i<=log(base3)(n) and : for n>50 3^( ...
0
votes
1answer
46 views

Running time of recursive algorithm with geometric series

What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$? So far I have: $ O(n) \le cn$ for some constant $c$ Hence: $$T(n) \le 3T(\frac{n}{2}) + cn$$ After a recursion: $$T(n) \le ...
0
votes
0answers
15 views

Running time of recursive algorithm [duplicate]

An algorithm solves problems of size $n$ by recursively solving two subproblems of size $n - 1$ and then combining the solutions in constant time. What is the algorithms running time? Assume $ ...
0
votes
1answer
77 views

Algorithm to compute a recursive function on a given set [closed]

I am working on a property of a given set of natural numbers and it seems difficult to compute. There is a function 'fun' which takes two inputs, one is the cardinal value and another is the set. If ...
0
votes
1answer
18 views

Solution to the following recurrence relation and initial condition? [duplicate]

With the initial condition being $a_0$ = 3, and the relation being $a_n = 2a_{n - 1}$, what would the solution be? Any help would be greatly appreciated.
0
votes
1answer
58 views

How to solve this recurrence using recursion tree method

How to solve this using the recursive tree method? I'm stuck with the $\max$. $$T(n) = T\left(\left\lceil \frac{n}{\max\,\{\sqrt{n},2\}}\right\rceil\right) + n\,.$$
0
votes
0answers
35 views

why this recurrence can be solved by Master method? [duplicate]

I have studied the following recurrence. The ratio between f(n) and n^log_b(a) is log n so there is non polynomial difference but I have studied from book that it can be solved by master method. $T ...
0
votes
1answer
28 views

Problem with Understanding a Recursion Tree

Consider the recursion tree: $T(p) = 3T(\frac{2p}{8}) + 2T(\frac{p}{8}) + O(p)$. I determined that there are at most $1 + log_{4}\ p$ levels, because the longest simple path from root to leaf is $p ...
1
vote
1answer
84 views

How to write recurrence relation for the following scenario?

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function $g(x)$ for each node x. If the cost of computing $g(x)$ is min{no. of leaf-nodes in ...
0
votes
2answers
58 views

Solution verification: solving $T(n) = T(n-1) + 2/n$

I was wondering if someone could possibly verify my solution to the following: I'm trying to solve the recurrence relation $T(n) = T(n-1) + 2/n$. To get it into the form of the Master Theorem, I note ...
0
votes
0answers
32 views

Solving $T(n) = 7T(n/2) + n^2 + \log(n)$ [duplicate]

I'm working on a problem set for my algorithms course and we're asked to solve the recurrence relation $$ T(n) = 7T(n/2) + n^2 + \log(n). $$ Since this recurrence relation is not of the form $T(n) = ...
-1
votes
1answer
39 views

Solving Recurrence Relations 3 [closed]

Consider the following recurrence $$T(n)=T(n-1)+n\log n$$ My approach: Solving using Substitution $T(n)=n \log n+(n-1) \log (n-1)+(n-2) \log (n-2)+(n-3) \log (n-3)+...$ $=[n\log n + n \log(n-1)+ n ...
0
votes
0answers
18 views

Approximating Recurrence Relations [duplicate]

Consider the following recurrence relation $$T(n)=2\times T(n-1)+n$$ $$T(1)=1$$ My approach: On Solving using Substitution I ended up here $2^{n-1}T(1)+2^{n-2}T(2)+...+2^2(n-2)+2(n-1)+n$ How to ...
1
vote
1answer
39 views

Prove by Induction that $r_n$ is $O(\log_2(\log_2n))$ [duplicate]

Let the sequence $r$ be defined by: $$\begin{align*}r_{1} &= 1\\ r_n&= 1 + r_{\lfloor\sqrt{n}\rfloor}\,,\quad n\geq 2\,.\end{align*}$$ Prove by induction that $r_n$ is $O(\log_2(\log_2n))$. ...
1
vote
1answer
10 views

Finding a solution to the following conditions? [duplicate]

So for these 5 conditions, I am trying to find the solution/formula for them. What would $a_n$ equal basically? If it helps, the recurrence relation these 5 conditions were generated from was $a_n = ...
9
votes
3answers
447 views

Efficient algorithm to compute the $n$th Fibonacci number

The $n$th Fibonacci number can be computed in linear time using the following recurrence: ...
0
votes
1answer
36 views

Merge Sort proof [duplicate]

I am trying to prove that merge sort is indeed $O(n \log n)$. I was able to extract a pattern using constants, however now I am stuck. This is as far as I can get: $T(n) = 2T(n/2) + cn$ $T(n/2) = ...
5
votes
1answer
54 views

Why is $\sum_{j=1}^{n-1}[\Pi_{k=1}^{j}[(n-k)]]=2^n$?

In CLRS book, in the road cutting example there is a recursion formula $$ 1+\sum_{j=0}^{n-1}T(j) $$ and it can be proved that the sum is $$ 2^n $$ by simple induction. In 3-rd ...
1
vote
1answer
36 views

Solving recurrence relation

I am trying to find a $\Theta$ bound for the following recurrence equation: $$ T(n,p,k)=T(n,p,k/2)+T(n,p/4,k)+T(n/8,p,k)+npk $$ ...
0
votes
1answer
60 views

Solving a recurrence relation using Divide and Conquer Master Theorem [duplicate]

For the recurrence relation $$T(n) = 16T(n/4) + n!\,,$$ I have found that $T(n)\in Θ(n!)$. Can this be deduced using the Master Theorem?
2
votes
1answer
67 views

Closed-form solution to recurrence equation

I have a recurrence relation of the form: $f(0) = f(1) = 1, f(2) = 2$ (initial conditions). $f(2n) = f(n+1) + f(n) + n$ for $n>1$. $f(2n+1) = f(n) + f(n-1) + 1$ for $n>1$. I have been able ...
3
votes
2answers
70 views

If $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?

$T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$ $T(1)=1$ The value of $T(m^2)$ for m ≥ 1 is? Clearly you cannot apply master theorem because it is not of the form ...
1
vote
1answer
52 views

What is the correct representation of Master Theorem?

What I'm taught in my class - $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$ where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number. if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$ if ...
1
vote
1answer
89 views

What kind of recurrence relations has p < 0?

By the master method, $T(n) = aT(\frac {n}{b})+\Theta(n^k\log^pn)$ where $p$ is real. I know $\log^4n=\log(\log(\log(\log n)))$ but how do you calculate something like $\log^pn$ where $p<0$?
3
votes
1answer
495 views

How many comparisons do we need to find min and max of n numbers?

Suppose we have given a list of 100 numbers. Then How can we calculate the minimum number of comparisons required to find the minimum and the maximum of 100 numbers. Recurrence for the above problem ...
6
votes
1answer
80 views

Solving recurrence relation $T(2n) \leq T(n) + T(n^a)$

I want to prove that the time complexity of an algorithm is polylogarithmic in the scale of input. The recurrence relation of this algorithm is $T(2n) \leq T(n) + T(n^a)$, where $a\in(0,1)$. It ...
0
votes
0answers
24 views

What kinds of recurrence relations can be involved in a tabulation solution?

We all know F(n) = F(n-1) + F(n-2) is an easy example. We can compute this by using DP. But what about F(n) = F(n-1) + k, we could compute this by tabulation but would you still call it DP? Also, ...
3
votes
1answer
71 views

Making a conjecture of a closed form

There's a formula given $$ T(m,n) = \left\{ \begin{array}{l l} 1 & \quad \text{if $m=0$}\\ 1+T(n \mod m, m) & \quad \text{if $m>0$} \end{array} \right.$$ We're told to use ...
1
vote
0answers
33 views

Is there a closed-form formula for this recursive sequence? [duplicate]

Let $k > 0$ be an integer. Define $A_n$ as follows: $$ A_n = \begin{cases} n & \text{if } n < k, \\ \sum_{i=0}^{k-1} i & \text{if } n = k \\ \sum_{i=1}^k A_{n-i} & \text{if } n ...
0
votes
1answer
38 views

Solve a recurrence relation with two recursion calls using the iteration method [duplicate]

I can't figure out how to solve this recurrence relation using the iteration method: $$T(n) = \begin{cases} 0, & \text{if $n=0$} \\ 1, & \text{if $n=1$} \\ 3T(n-1)+ 4T(n-2), & \text{if ...
0
votes
2answers
93 views

recurrence - Iteration method T(n)=T(n-a)+n [duplicate]

I really need help to solve the following: T(n)=T(n-a)+n where a is a constant greather or equal 1. So I started to iterate T(n)=T(n-a)+n =T(((n-a)+n)-a)+n =T(3n-3a)+n ...
2
votes
1answer
107 views

Which algorithms have runtime recurrences like $T(n) = \sqrt{n}\,T(\sqrt{n}) + O(n)$?

The algorithms using the "divide and conquer" (wiki) design strategy often have the time complexity of the form $T(n) = aT(n/b) + f(n)$, where $n$ is the problem size. Classic examples are binary ...