Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.

learn more… | top users | synonyms

0
votes
3answers
42 views

HOW TO: Recurrence Relation $T(n) = 2T(n^\frac{1}{2}) + c$

I've been trying to do this for hours. I just don't know how. I'm familiar with recurrence relations in the form of $T(\frac{n}{2})$, but what do you need to do to solve $T(n^\frac{1}{2})$? I've ...
2
votes
2answers
49 views

Recurrence Relation for Strassen

I'm trying to solve the following recurrence relation (Strassen's):- $$ T(n) =\begin{cases} 7T(n/2) + 18n^2 & \text{if } n > 2\\ 1 & \text{if } n \leq 2 \end{cases} ...
-2
votes
1answer
17 views

give a tight asymptotic upper bound (() notation) on the solution to each of the following recurrences.

give a tight asymptotic upper bound (() notation) on the solution to each of the following recurrences. T(n)=T(n/3) + T(n/4) + 5n
-2
votes
0answers
20 views

True or False let f(n) and g(n) be asymptotically nonnegative functions then at least one relationship of f(n)=O(g(n)) and g(n)=O(f(n)) [closed]

let f(n) and g(n) be asymptotically nonnegative functions then at least one relationship of f(n)=O(g(n)) and g(n)=O(f(n))
0
votes
0answers
19 views

Asymptotic complexity Order the following functions with respect to their growth rates, . Explain your reasoning. [closed]

Asymptotic complexity Order the following functions with respect to their growth rates, from the slowest growing to the fastest growing. Explain your reasoning. a. 2^log n b.√2 c.(√2)^log n d.(log ...
1
vote
2answers
23 views

Tight asymptotic upper bounds on specific recurrences

give a tight asymptotic upper bound (() notation) on the solution to each of the following recurrences. $T(n)=2T(n/8) + \sqrt[3]n$ $T(n)=T(n/3) + T(n/4) + 5n$
6
votes
1answer
37 views

Another recurrence… $T(n)=\sqrt{2n} \cdot T(\sqrt{2n}) + \sqrt{n}$

I'm trying to solve the following recurrence : $$T(n)=\sqrt{2n}\cdot T(\sqrt{2n}) + \sqrt{n}$$ I've tried substituting $n$ for some other variables to transform the above to something easier without ...
1
vote
1answer
20 views

Solving recurrenc using recurrence tree method.

I got this recurrence to solve: $T(n) = 2.1 T(n/2) + n$. I know the answer (got it using the plug and chug method and using the master method too), but I'm trying to solve using recurrence tree and ...
0
votes
2answers
210 views

Proof by the substitution method that if $T(n) = T(n - 1) + \Theta(n)$ then $T(n)=\Theta(n^2)$

How to prove by the substitution method that if $T(n) = T(n - 1) + \Theta(n)$ then $T(n)=\Theta(n^2)$? I've tried the following and got stuck $$ \begin{align} T(n) &= T(n - 1) + \Theta(n) \\ ...
2
votes
0answers
11 views

Repertoire method for solving recursions

I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics: $g(1) = \alpha;$ $g(2n+j) = 3g(n) + γn + β_j$ : j = 0,1 and n >= 1 I have assumed the closed form to ...
0
votes
2answers
36 views

Equation of a curve whose difference in ordinate values form an arithmetic sequence

I have the following recurrence equation that I have obtained while trying to solve a problem:- $$T(0) = 1$$ $$T(n) = T(n-1) + 9n - 8: n \ge 1$$ The values of $T(n)$ for $n = 0,1,2,... $ are as ...
1
vote
1answer
36 views

Generalized Josephus problem

I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as f(1) = a f(2n) = 2f(n) + b, for n >= 1 f(2n+1) = 2f(n) + y, for n >= 1 ...
1
vote
0answers
50 views

How to deduce the results of response time by this trajectory approach?

First, we denote this: And And we get this right property( $last_i$ means the last node on $τ_i$): And: $Smin_i^h$ = $\sum_{h'=first_i}^{h-1} ({C_i^{h'} + L_{max})}$ $Smax_i^h$ = ...
0
votes
0answers
48 views

How to find integer solutions of an equation using approximation methods?

If I have a function called $f(x)$ that have several roots, integers and not integers. How can I find just the integer ones by approximations methods? A simple example would be ...
4
votes
2answers
165 views

unorthodox solution of a special case of the master theorem

I am asking for references regarding a special case of the master theorem. This theorem seems to appear quite a lot on this site, prompting me to study it in more detail, e.g. see my posts here and ...

1 2 3 4 5 14
15 30 50 per page