All Questions
31
questions
-2
votes
2
answers
102
views
i need help with this recursive problem: $T(n) = nT(n-1) + 1$, $T(0) = 0$. [closed]
Now here I solved everything but I’m now stuck at the general form how am I gonna write the general form with the (pi) product summation ?
Hint there’s something related also with combination and ...
- 11
4
votes
1
answer
285
views
Printing neatly
I'm working on the following problem (which is not my actual question)
Consider the problem of neatly printing a paragraph with a monospaced font (all
characters having the same width). The input ...
- 910
0
votes
2
answers
113
views
Solving the following recurrence equation $T(n) = T(n-2)+n^2$, having $T(0)=1$, $T(1)=5 $
Solve the following recurrence equation: $T(n) = T(n-2)+n^2$, having $T(0)=1$, $T(1)=5$.
I need to solve this equation but when I get to the particular solution with $n^2$ some of the terms I need ...
- 1
2
votes
1
answer
279
views
Recurrence relation of Sn that depends on Sn-1
OK, so I have run into this weird question about recurrence relations that I cannot complete by myself (first year comp. sci. student and first discrete math class, studying by myself). To help you ...
user764644
0
votes
1
answer
161
views
Solving recurrence relation with non-constant coefficient.
I am facing difficulty in solving this recurrence relation having non constant coefficients. Kindly help
$nT(n) = (2n - 2)T(n - 1) + \log_2 (n/(n-1)^2) , \space\space T(1) = 2$.
EDIT:
$(n^2) T(n) = (...
0
votes
1
answer
170
views
Using the master theorem to find an expression for T(n) in Big Oh
Solve the recurrence relation $T(n)$ = $2T$($\frac n 3$) + $c\sqrt2^{logn}$
, T(1) = 1, by finding an expression for T(n) in big-Oh notation.
So I'd like to solve this using the master theorem but I ...
- 667
0
votes
1
answer
98
views
Understanding the recurrence relation T(n) = c(T(n/c) + 1)
Solve the recurrence relation T(n) = c(T(n/c) + 1), T(1) = 1, by finding an expression for T(n) in big-Oh notation.
Think about inputs of the form $c^k$.
$$T(c^k)=cT(c^{k-1})+c=c^2T(c^{k-2})+c^2+...
- 667
0
votes
1
answer
98
views
Solve the recurrence relation $T(n) = c(T(n/c) + 1), T(1) = 1$, by finding an expression for $T(n)$ in big-Oh notation.
I'm a complete beginner at this, and was having trouble with this problem.
looking at $T(n) = c(T(n/c) + 1)$. I'm pretty sure its in the form of
f(n) = af(n/b) + Cnd
I think the master theorem ...
- 667
0
votes
1
answer
474
views
How do you solve a linear recurrence relation for $a_{n}$ given the solution
I'm a beginner who is starting to learn about linear recurrence relations. I've just come across a problem where I'm not sure how to progress.
Going off of my notes linear recurrence was solved ...
- 667
0
votes
1
answer
587
views
Recurrence Relation, Compound Annually
If I invest $\$2000$/yr in a tax sheltered annuity at $7\%$, where $A_n$ is the amount at $n$ years... what is the recurrence relation? I know my initial condition $A_0$ is $2000$. And for some reason ...
- 1
1
vote
1
answer
55
views
0
votes
1
answer
20k
views
Solutions of recurrence relations $T(n) = 2T(n-1)$ and $T(n) = 2T(n-1) - 1$
Consider the recurrence equation
T(n) = 2T(n-1), if n>0
= 1, otherwise
Then T(n) is (in big O order)
...
- 4,785
0
votes
2
answers
2k
views
When applying the master theorem, how to decide on case 1, 2, or 3?
When you are given a relation, such as $$T(n)=8T\Big(\frac{n}{2}\Big)+160n,$$
what are the logical steps to consider when deciding whether to apply case 1, 2, or 3? Or do you have to apply all 3 and ...
- 874
1
vote
2
answers
79
views
Prove the following fact about a recurrence relation
Consider the following recursive relation:
$$T(1)=1$$
$$T(n)=2T\left(\left\lfloor \frac n 2\right\rfloor\right)\text{ for }n\geq 2$$
It is required to show that
$$T(n)=2^{\lfloor \log_2 n\rfloor}$$
I ...
- 9,258
2
votes
2
answers
567
views
Solving Recurrence Relation with substitution
How to solve T(n) = T(n-2) + n using iterative substitution
Base case:
T(0) = 1
T(1) = 1
Solve:
T(n) = T(n-2) + n
Currently I have:
...
- 215