All Questions
Tagged with recursive-algorithms summation
29
questions
-4
votes
1
answer
129
views
Solving the recurrence $T(1) = 1$, $T(n) = T(n-1) + n^2$ [duplicate]
How do you solve the following recurrence?
$T(1) = 1$
$T(n) = T(n-1) + n^2$
0
votes
1
answer
39
views
Exponentially discounted running average: a computer implementation
I need to write a computer algorithm that calculates the following exponentially discounted running average
\begin{equation}
\hat{u}(t) = \lambda \int_0^t u(s) \exp{\left[-\lambda(t - s)\right]} ds\,,
...
- 267
-1
votes
1
answer
82
views
How to minimize a summation function [closed]
My question is: How do we minimize a function like this with find a constant number for x?
in another word, we have a set and "i" is a member of that set and we should find a constant number ...
2
votes
2
answers
143
views
How to simplify the summation of a recurrence relation
After solving the recurrence relation
$$T(n) = 3T(\frac{n}{3}) + n\log(n)$$
I get following equation
$$T(n)=3kT(\frac{n}{3k})+ n\log(n) + n\log(\frac{n}{3}) + n\log(\frac{n}{3^2})+\dots+n\log(\frac{n}{...
- 21
0
votes
1
answer
326
views
(Calculus) Solving a geometric series word problem
I’m struggling with understanding how to solve part B of the following problem:
Consider an outdoor pool initially filled with 20,000 gallons of water. Each day, 4% of the water in the pool ...
- 11
0
votes
1
answer
42
views
Finding $\sum_{i=0}^{\log_2\log_2n} n^{\frac{2^{i+1}-1}{2^i}}$
I have a task on finding runtime complexity of an algorithm. I worked out the following summation expression, unsuccessfully tried to get a result from Wolfram Alpha, have no idea in what direction I ...
- 3
1
vote
0
answers
173
views
Minimize repeated summation of numbers
I recently came across this post
The solution given is elegant and it got me thinking. What if we are not allowed to sort the list and can only take 2 adjacent elements i.e at indcies $x,x+1$ (this ...
- 77
1
vote
1
answer
152
views
Solving $\begin{cases} T_{0}=5 \\ 2T_{n}=nT_{n-1} + 3n! \end{cases}$ using method of summation factors
I need to solve the following recurrence relation using "method of summation factors".
$\begin{cases} T_{0}=5 \quad \quad \quad \quad \quad\quad\quad \iff n=0\\ 2T_{n}=nT_{n-1} + 3n! \quad \quad \iff ...
- 1,392
1
vote
3
answers
72
views
Summation formula for this?
I have found the following summation formula based on a recurrence. It supposes $n = 2^k$ where k is an integer. I've intuitively discovered that the following closed form may be true (following the ...
- 15
0
votes
0
answers
29
views
How to prove that a recursive function with inner summation is approximately equal to some closed-form equation?
The following problem is taken from an algorithms textbook(specifically, in the context of complexity analysis of recursive algorithms.)
Starting from the equation:
$$nf(n) = n(n-1) + 2 \sum_{k=1}...
- 111
1
vote
2
answers
84
views
Leaving recurrence summation in terms of $k$, $\sum_{i=0}^{k-1}\frac{3^i\sqrt{\frac n{3^i}}}{\log\frac n{3^i}}$
I have an exercise where I need to use the substitution method to solve the following recurrence and determine their corresponding complexity.
$$t(n)=3t(n/3) + \frac{\sqrt n}{\log n}$$
After some ...
- 45
0
votes
3
answers
536
views
Solving a recurrence relation: can't figure out how to convert from summation
I am really struggling to solve this recurrence.
$$
T(n) = T(\sqrt{n}) + n.
$$
I am asked to give asymptotic upper and lower bounds for $T(n)$. I am free to use any method to arrive at my answer, ...
- 37
1
vote
0
answers
37
views
Trouble understanding a recursive summation
I'm reading an NLP paper. In section 4.2, there is the following summation:
$$\alpha[t][k] = \sum^{t-k}_{j=1}p(c^t_{t-k+1} | c^{t-k}_{t-k-j+1}) \cdot \alpha[t-k][j]$$
where $\alpha[0][0] = 1$.
$\...
- 265
0
votes
0
answers
50
views
0
votes
1
answer
102
views
Explicit form of recursive function
Given recursive function:
$$T(x)=2T(\frac{x}{2})+\frac{2}{\log (x)}$$
reach an explicit form:
We already solved it in class. However I can't seem to remember, how was it...
I Wrote it in these ...
- 650