5 votes
Accepted

Summation of time complexity for a diminishing for loop with logarithmic runtime.

The things being added are not the values $i$ assumes, but whatever goes on inside the loop, which here is an $O(1)$ operation. There is also no reason why everything should be multiplied by $n$ ...
  • 92.5k
3 votes
Accepted

Efficent algorithm for find the subset of a set of 8 bit integers, whose elements do not contain each other which has the maximum number of elements

Sperner's theorem: an antichain of subsets of a set of $n$ elements has cardinality at most $${n \choose \lfloor n/2 \rfloor}$$ In this case $n=8$, and the antichain consists of all $8$-bit integers ...
1 vote

Formulating list sorting as a pure math problem

I have been struggling with this as well, Now that I'm taking some Theoretical Pure Math courses... I was trying to redefine or attempt to get a 'static' definition of Algorithm and not trying to use ...
1 vote

graph - Modifications to Dijkstra algorithm for single source longest path problem

The longest path starting from a vertex cannot be found in polynomial time [polynomial in the size of the input that is] unless P=NP. Indeed, if we can find the longest path starting from a vertex in ...
  • 16.4k
1 vote

Prerequisites for Computational Mathematics

Depends on what sort of field you want to learn about. I would recommend taking an intro to "Numerical Analysis" course, which usually just requires a basic proofs/calculus background. ...
  • 3,799
1 vote

Quick General Question regarding Interior Point Methods

Equality constraints are naturally supported by IPM. They simply appear "as is" in the KKT conditions and linearized in the linear system (augmented or KKT system) resulting from the Newton ...
  • 895
1 vote
Accepted

Find upper bound for T(n) in terms of n and prove with Master Theorem

Since the critical exponent is $\log_32$ and $f(n)$ is $\Omega(n^{\log_32})$, only the third (supercritical) case of the master theorem applies and we have to use the regularity condition $$2f(n/3)\le\...
  • 92.5k
1 vote
Accepted

How can I solve this piecewise recurrence relation?

For any odd $n \ne 1$, $T(n) = T(n-1) + \Theta(n)=2T\left(\frac{n-1}{2}\right) +\Theta(n)+\Theta(n) = 2T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) +\Theta(n)$ Now just use master Theorem or ...
  • 175

Only top scored, non community-wiki answers of a minimum length are eligible