# Tagged Questions

26 views

### Analyze the following recurrence relation.

I'd like to express the following recurrence relation as the number of multiplications it performs, and then again but this time as the number of additions/subtractions it performs. ...
73 views

### Solving recurrence relation: f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3

f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3 I have attempted to solve it by letting n = 2k f(2k) = 3f(2k-1) - 2f(2k-2) Then set S(k) = f(2k) S(k) = 3*S(k-1) - 2*S(k-2) ...
31 views

### Why does $T(n) \leq 2 T(\lceil \frac{n}{2} \rceil)+\mathcal{O}(n)$ imply $T(n)=\mathcal{O} (n\log(n))$

I am learning about sort algorithms and their complexities. For merge sort, I'm confronted with $T(n) \leq 2 T(\lceil \frac{n}{2} \rceil)+\mathcal{O}(n)$. The author makes the claim with no ...
46 views

### Help understanding Recursive algorithm question

We have a function that is defined recursively by $f(0)=f_0$, $f(1)=f_1$ and $f(n+2) = f(n)+f(n+1)$ for $n\geq0$ For $n\geq0$, let $c(n)$ be the total number of additions for calculating $f(n)$ ...
117 views

### find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
28 views

### Big-O evaluation:

I have the expression: $$f_{k}(n,m) = (n - k)(m - k) + f_{k+1}(n,m)$$ which runs until k = n or m. What is the big theta of this function in terms of n,m? A naive approach is to assume that m does ...
2k views

### Upper bound for $T(n) = T(n - 1) + T(n/2) + n$ with recursion-tree

I'm reading through Introduction to Algorithms, 3rd ed. and I got stuck on the following recurrence (exercise 4.4-5): $$T(n) = T(n - 1) + T(n/2) + n$$ The exercise asks you to find the upper bound ...
160 views

### Solving a recurrence relation with floors and comparing it with other complexity classes

The problem that I am struggling with is the recurrance relation $T(n) = \lfloor(T(n/2))\rfloor + \lfloor(log \space n)\rfloor$ Where $T(1) = 1$ I am supposed to answer true/false to each of the ...
68 views

### Solving recurrences of the form $T(n) = aT(n/a) + \Theta(n \log_2 a)$
The time complexity for the merge sort algorithm is $T(n) = 2T(n/2)+\Theta(n)$, and the solution to this recurrence is $\Theta(n\lg n)$. However; assume you are not dividing the array in half for ...
### Analysis of Algorithms: Solving Recursion equations: $\quad T(n)= T(cn)+T(dn)+n$
How can I prove that the solution for the following recursion equation is $\Theta(n)$: $$T(n)= T(cn)+T(dn)+n \text{ for } d,c>0 \text{ and } c+d<1$$ Edit: $cn$ on one side only. What I need to ...