Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
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 ...