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

learn more… | top users | synonyms

2
votes
1answer
37 views

Bounding the recurrence $f(n)=2f(n-1)+2f(n/2)$

I met a recurrence equation for my algorithm $$ f(n) = 2\cdot \left( f(n-1) + f(\frac{n}{2}) \right)$$ with $f(1)=1$, $f(2)=4$, $f(3)=10$. I guess it is $\Theta((2+\epsilon)^n)$, where $\epsilon$ ...
0
votes
0answers
16 views

Iteration method - recurrence [duplicate]

How can I find the tightest possible asymptotic bounds on the recurrence T(n) = 3T(n/2)+cn, where c is a positive constant. Must use iteration method.
3
votes
2answers
56 views

Solve the worst case of this recurrence equation

I am trying to find the worst case $Θ$ bound for the following recurrence equation: $$ T(n)=\sum_{i=1}^kT(a_i)+n+\lg k\sum_{i=1}^ka_i\quad where\quad n=1+\sum_{i=0}^ka_i\quad and\quad a_0\ge a_1, a_2, ...
2
votes
1answer
43 views

How to make this recursive relationship nonrecursive? [closed]

I need to make a recursive relationship for a function f(m, n) nonrecursive to make it more efficient and succinct in my code. I stumbled across an important ...
1
vote
1answer
59 views

Recurrence of T(n) = T(n/3) + T(2n/3) [duplicate]

I've searched online for this but I only seem to find answers for a similar equation: T(n) = T(n/3) + T(2n/3) + cn But the one I'm trying to solve is: ...
-1
votes
2answers
42 views

Solve recurrence [closed]

![enter image description here][1] I have a problem to solve this recurrence. I tried by myself but it doesn't look understandable. Solve the following recurrence
0
votes
3answers
136 views

Solve the recurrence $f(n+1)=f(n)^2,\, f(0)=2$ [closed]

I have a problem with an exercise asking me to solve the following recurrence: $$f(n+1)=f(n)^2, \quad f(0)=2$$ Can someone explain how to solve this? I tried but couldn't.
0
votes
2answers
57 views

How many times can you divide a list of n elements in 1/2 [closed]

I am trying to wrap my head around recursion and divide and conquer algorithms. Can someone provide a proof and explanation of how many times a list of n elements can be divided in 1/2 on both sides.. ...
0
votes
0answers
20 views

Time Complexity Problem [duplicate]

$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta ( n)$$ I have been trying to solve this question but I could not find anything. I tried to build recursion tree but I can not find the sum. Do you ...
0
votes
0answers
19 views

Time complexity by solving recurrence relation [duplicate]

I was working on recurrence relation and came across this example T(n) = 2T(n/2) + log(n) What will be the time complexity, ie, big O for this relation. Thanks for any help in advance.
2
votes
1answer
40 views

Recursive Algorithm Analysis

$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta (\lg n)$$ I have been trying to solve this question but I could not find anything. My approach: $n = 2^k$ $S(k) = T(2^n)$ and $S(k/2) = ...
-1
votes
2answers
78 views

Recurrence Problem $T(n) = 3T(n/3) + n$ [duplicate]

My question here is dealing with the residual that I get. We are trying to prove $T(n) = 3T(n/3) + n$ is $O(n*\log n)$. So where I get is $T(n) \le cn[\log n - \log 3] + n$. So my residual is $-cn\log ...
2
votes
1answer
31 views

Recurrence $T(n) = 2T(\sqrt{n}) + \log n$ [duplicate]

So I have a question for the recurrence $T(n) = 2T(\sqrt{n}) + \log n$. We are to use substitution method to figure out the solution. This is an example problem (not a exercise problem) in my book ...
3
votes
1answer
37 views

Recurrence relation in 2 variables

When analyzing an algorithm, the following recurrence relation popped up: $T(n,d)=2T(n/2,d)+T(n,d-1)+O(dn)$ where $T(n,1)=O(n \log{n})$ and $T(1,d)=O(d)$. By applying the Master Theorem ...
3
votes
1answer
38 views

How to solve recurrences involving log?

For example, $T(n) = \log {n} \cdot T(\frac{n}{\log{n}}) + \Theta(n)$ I tried using the substitution method with $ n = 2^m $, but that got me nowhere, since it still ends up with a $m$ and $2^m$. ...
0
votes
1answer
54 views

Series where each term is square of previous [closed]

The problem statement is as follows:- In a court case, a judge cited a court of contempt and ordered a fine of $2 for first day. On subsequent days, the fine would be equal to the square of the ...
1
vote
1answer
56 views
1
vote
2answers
73 views

Why can any polynomial and exponential be represented as a recurrence?

I posted this question on math.SE but I haven't got any reply so I'm posting here also. I am reading The Algorithm Design Manual by Steven S Skiena. In Section 4.10.1 Recurrence Relations, I ...
3
votes
1answer
28 views

Pick parameter function that minimises whole function

I have a recursive algorithm defined by the following recursion. $$T(n) = T(n/f(n)) + O(\log f(n)).$$ I want to find the function $f$ that minimizes $T(n)$. If $f$ is a constant then $T(n) = ...
2
votes
2answers
106 views

How to apply the substitution method to n/2?

I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it. In standard induction proofs you prove a base case, assume it holds for n ...
2
votes
2answers
107 views

Solution to recurrence $T(n) = T(n/2) + n^2$

I am getting confused with the solution to this recurrence - $T(n) = T(n/2) + n^2$ Recursion tree - ...
0
votes
1answer
69 views

Master theorem for $T(n) = 2T(n/2) + n^{2}\log n$

Would I use the third case of the Master Theorem for the recurrence equation $T(n) = 2T(n/2) + n^{2}\log n$? The condition given for the third case by Wikipedia is $f(n) = \Theta(n^c)$ when $c > ...
3
votes
3answers
71 views

How do I show T(n) = 2T(n-1) + k is O(2^n)?

This is a practice problem I've come up with in order to study for an exam I have in a couple of hours. Again, here's the problem: Show T(n) = 2T(n-1) + k is O(2^n) where k is some positive constant. ...
2
votes
1answer
141 views

Finding growth of “inter-recursive” functions

consider following code int f(int x) { if(x<1) return 1; else return f(x-1)+g(x); } int g(int x) { if(x<2) return 1; else return f(x-1)+g(x/2); } ...
-1
votes
2answers
79 views

Recurrence for total number of extraneous key insertions in a hash table

I have a practice exam question that I don't know how to set up a recurrence for. It is dealing with a hash table. The question is as follows: Suppose that a hashing strategy is designed so that ...
4
votes
0answers
49 views

Are there master theorems that deal with parameters of the form $n-c$?

While thinking about this question on a recurrence I checked out some stronger master theorems. Unfortunately, they do not seem to apply because terms $\qquad\displaystyle T(n) = \dots + T(n-1) + ...
6
votes
1answer
66 views

Why does Akra-Bazzi need that toll-function g is bounded?

Following up on vonbrand's answer I want to write a small document about stronger master theorems for our students, one of which is the Akra-Bazzi theorem. I have copied the theorem from their paper ...
0
votes
1answer
44 views

Pentary Search Recurrence Relation

I have done an assignment question which asks me to find the average case of pentary search. The one I came up with is: C(n) = C(n/5) + 14/5 However, I got it ...
0
votes
2answers
65 views

Recurrence Equation Question

I have some difficulty trying to tell which equation to use when I'm given an explanation on how an algorithm operates. Especially divide and conquer. Normally I see these kind of equations: ...
2
votes
1answer
551 views

Ternary Search Recurrence Relation

I am trying to work out the recurrence relation for Ternary Search. This is what I came up with: C(n) = C(n/3) + 2 However, I talked to my professor and he said ...
1
vote
1answer
83 views

Solving a complicated recurrence relation

How to solve the recurrence relation below? $$T(n) = \begin{cases} 2T(\sqrt{n}) + \log n/\log\log n & \text{if } n > 4\\ 1 & \text{if } n \leq 4. ...
1
vote
1answer
136 views

Recurrence Relations

I am trying to understand how to solve complex recurrence relations and whether there is a general method or technique to help me. That being said I am not talking about recurrence relations that can ...
1
vote
1answer
79 views

How to solve for recurrence with substitution or other methods? [duplicate]

Forgive me if I am new, I am trying to learn how to solve recurrences. I have the following recurrence: $$T(n) = 2 T(\lfloor\frac{n}{3}\rfloor) + \frac{1}{2} T(\lfloor\frac{2n}{3}\rfloor) + n^2 ...
2
votes
1answer
49 views

Running time and stack depth of a lisp recurrence

Consider the following sequence $a_n$: \begin{align*} a_0 &= \alpha \\ a_k &= \beta a_{k-1} + \kappa \end{align*} Now consider the implementation of this sequence via lisp: ...
1
vote
1answer
42 views

Help with recurrence solutions

We started learning recurrences and I am having trouble with some of the problems. Our professor is having us substitute in $n=2^m$ and $S(m)=T(2^m)$ then writing down equations and summing them all ...
0
votes
2answers
1k views

Solving recurrences using substitution method

I already have a solution for this problem but it's just not making sense to me. Here is the problem (It's from Introduction to Algorithms by CLRS found in CH.4): Show $T(n) = 2T(\lfloor n/2 ...
7
votes
1answer
172 views

Asymptotic approximation of a recurrence relation (Akra-Bazzi doesn't seem to apply)

Suppose an algorithm has a runtime recurrence relation: $ T(n) = \left\{ \begin{array}{lr} g(n)+T(n-1) + T(\lfloor\delta n\rfloor ) & : n \ge n_0\\ f(n) & : n < n_0 ...
4
votes
1answer
132 views

Do different variants of Mergesort have different runtime?

One of my courses introduced the following question: Given the recurrence relation for mergesort: $T(n) = 2T(n/2) + n$ How would the following parameter passing strategies influence the ...
2
votes
1answer
217 views

Selection in expected linear time: Why am I getting $O(n)$ bound instead of $\Omega(n \lg n)$? [duplicate]

The problem is from CLRS 9.3-1: In the algorithm SELECT, the input elements are divided into groups of $5$. Argue that ...
0
votes
1answer
91 views

Relation between the number of sub-problems ($a$) and the size of sub-problems ($b$) in a recurrence

Below is a well-known equation for generalized recurrence relation in a divide and conquer paradigm (as described in CLRS) -- $$T(n) = aT(n/b) + f(n), \quad \text{where} \quad a \gt 1 \text{ , } b ...
1
vote
1answer
151 views

Recurrence formula for a known sequence?

Problem: How do we can generate some mathematical close form of the following sequence, which has following 256 entries: 1 7 7 7 7 9 9 9 7 9 9 9 7 9 9 9 7 11 11 11 ...
1
vote
1answer
2k views

Recurrence for recursive insertion sort

I tried this problem from CLRS (Page 39, 2.3-4) We can express insertion sort as a recursive procedure as follows. In order to sort A[1... n], we recursively ...
3
votes
2answers
81 views

Why is this sequence of recurrence relevant?

I am learning how to solve the time complexity for the recurrence relation $$ T(n) = 2T(n - 1) + n^2\text{, where }T(1) = 1 $$ The solution notes that I should begin by considering the following ...
6
votes
1answer
131 views

Semi-local Levenshtein distance

If you have a long string of length $n$ and a shorter string of length $m$, what is a suitable recurrence to let you compute all $n-m+1$ Levevenshtein distances between the shorter string and all ...
1
vote
0answers
122 views

How to prove the asymptotic upper bound for $T(n) = 2T(\lfloor n/2\rfloor + 17) + n$ is $O(n \log n)$? [duplicate]

I met the problem Show that the solution to $T(n) = 2T(\lfloor n/2\rfloor + 17) + n$ is $O(n \log n)$ while reading Introduction to Algorithm. It's a question about the substitution method for ...
-1
votes
2answers
76 views

Compare speed of two algorithms?

$$T(n) = 2T(n/2) + \Theta(n), n > 1$$ $$T(n) = \Theta (1), n \le 1$$ $$G(n) = G(\lfloor n/2 \rfloor) + G (\lceil n/2 \rceil) + \Theta(n), n > 1$$ $$G(n) = \Theta (1), n \le 1$$ Prove $T(n)$ ...
4
votes
1answer
161 views

Hanoi tower with forbidden direct move from source to destination

I want to know what is algorithm and time complexity of Hanoi tower with forbidden direct move from source to destination (it means you cannot move disk from source to destination directly and you ...
0
votes
1answer
221 views

Register Machine code for Fibonacci Numbers

I am not sure whether this is the right place to ask this question. I would like to write a register machine code which when given an input of n in register 1, returns (also in register 1) the nth ...
2
votes
1answer
115 views

Cost at Each Level of a Recursion Tree

Given a recursive function $T(n)=T(a_1\cdot n)+\dots +T(a_k\cdot n)+\Theta(n)$ such that $\forall a_i: 0<a_i<1$, what is the most general thing I can say about the sum of the cost of the nodes ...
1
vote
1answer
75 views

Resolving this recurrence equation [duplicate]

I have this recurrence equation: $T(n) = T(n/4) + T(3n/4) + \mathcal{O}(n)$ $T(1) = 1$ I know that the result is $\mathcal{O}(n \log n)$ but i don't know how to proceed.