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

learn more… | top users | synonyms

0
votes
0answers
34 views

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

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
178 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
38 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
62 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
27 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
12 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
31 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
69 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
14 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
40 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
34 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
25 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
70 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
57 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
31 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
38 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
37 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
9 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
203 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
34 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
50 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
31 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
56 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
64 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
66 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
46 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
295 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
76 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
23 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
61 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
37 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
63 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
94 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 ...
0
votes
1answer
25 views

Prove the upper bound on $T\left(n\right)=T\left(\log_{2}n\right)+O\left(\sqrt{n}\right)$ [duplicate]

I need some help with the following recursion: $T\left(n\right)=T\left(\log_{2}n\right)+O\left(\sqrt{n}\right)$ More specifically I wish to find and prove the upper bound on it. I have a hunch it ...
1
vote
0answers
16 views

How to solve the following recurrence: g(n) = g(log n) + n^(1/2) [duplicate]

Doesn't fit the Master method, and I am not sure where to go from here. Thanks
3
votes
1answer
43 views

Can anyone explain why this is an inadmissible recurrence case that cannot be solved by the master theorem?

Wikipedia says that the following recurrence is inadmissible since there is a non-polynomial difference between $f(n) = \frac{n}{\log n}$ and $n^{\log_b a}$: $$ T(n) = 2T\left(\frac{n}{2}\right) + ...
0
votes
1answer
83 views

Recurrence relation with a number value (not n) [duplicate]

I'm learning how to use recursion trees to solve recurrence relations and while I know how to solve it for the form $$T(n) = aT\big(\frac{n}{4}\big) + n$$ I'm stuck when the equation has a numerical ...
0
votes
0answers
37 views

Setting up a recursion tree

My textbook shows that when setting up a recursion tree for a recurrence, like $$T(n) = 3T\big(\frac{n}{4}\big) + cn^2$$ you place the cn^2 term at the root to represent the cost of at the top level ...
6
votes
1answer
752 views

What is the Big O of T(n)?

I have a homework that I should find the formula and the order of $T(n)$ given by $$T(1) = 1 \qquad\qquad T(n) = \frac{T(n-1)}{T(n-1) + 1}\,. $$ I've established that $T(n) = \frac{1}{n}$ but now ...
0
votes
0answers
26 views

Proof of the base case of Big Theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. a and c are positive constants. $T(n)=a$, if $n=2$ $T(n)=2T(n/2)+cn$ if $n>2$ Use induction to prove that ...
1
vote
1answer
93 views

Proof of big theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants. $T(n) = a$, if $n = 2$ $T(n) = 2T(n/2) + cn$ if $n > 2$ Use induction to prove ...
1
vote
1answer
58 views

Can there exist a recurrence relation for “sequential search”?

I'm just confused, cause from my knowledge recurrence is applied mostly to recursive procedures or divide and conquer techniques etc.
8
votes
1answer
271 views

Solving recurrence relation with two recursive calls

I'm studying the worst case runtime of quicksort under the condition that it will never do a very unbalanced partition for varying definitions of very. In order to do this I ask myself the question ...
1
vote
0answers
9 views

Trying to understand the iterative method for solving recurrences in this example [duplicate]

This question: Solving the recurrence T(n) = 3T(n-2) with iterative method has a pretty straightforward step-by-step for solving this particular recurrence. But, I'm having trouble understanding two ...