# Tagged Questions

93 views

### Solving the recurrence relation $T(n) = T(n-\sqrt n) + 1$

I have an algorithm that at each step can discard $\lceil\sqrt(n)\rceil$ possibilities at a cost $1$. The solution to the recurrence relation below is related to the question of complexity of such ...
32 views

### Checking if integer solutions exist

I have a linear equation $\alpha_1a_1+\alpha_2a_2+\dots=\beta$. I only need to check is there exists α1,α2... such that all are greater than or equal to zero. I am a computer science student , i got ...
20 views

### Verify that this recurrence relation is in O(log n)

For the recurrence $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ is in $\Theta(lg n)$ My attempt at a solution (mostly just wanting to verify its correct). Lower Bound: $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ ...
23 views

### How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity if we have 3 rods. So for example disk 2 can't be placed on disk 4, or disk 1 can't ...
45 views

### Cyclic tower of hanoi problem [duplicate]

If I have 3 rods in a circle and it is allowed to move the disks only in the clockwise direction. How many moves is necessary to move n disks from first rod to the third rod?
42 views

### Calculate a recursive equation in terms of theta

I am struggling with the following equation for one week! Please help me solve it. $$T(n)=T(\frac{n}{2})+\frac{n}{logn}$$ So far, I have come to the equation $T(n)=\Sigma \frac{2^x}{x}$
109 views

145 views

### How to find a closed form formula for the following recurrence relation?

I have to find a closed form formula for the following recurrence relation which describes Strassen's matrix multiplication algorithm - $$T(n) = 7\,T\left(n \over 2\right) + \frac{18}{16}n^2$$ with ...
By using the induction I have to the following recurrence solves to $T(n) = \Theta(n)$. $T(n) = T(\lfloor n/2\rfloor) + T(\lfloor n/7\rfloor) + 2n, T(0) = 1$
### Finding Pareto optimal solution set in $O(n \log n)$ time
http://cs-people.bu.edu/kvodski/teaching/spring10/lab7.html says: For two points in 2-dimensional space, point ($x_i$, $y_i$) dominates ($x_j$, $y_j$) if $x_i > x_j$ and $y_i > y_j$. Given a ...