The analysis-of-algorithms tag has no wiki summary.
12
votes
1answer
162 views
Polynomial speedups with algorithms based on semidefinite programming
This is a followup of a recent question asked by A. Pal: Solving semidefinite programs in polynomial time.
I am still puzzling over the actual running time of algorithms that compute the solution of ...
2
votes
0answers
397 views
Tricky big-O calculation
I have a recursive algorithm in which the time for each step depends on the time for smaller steps. Essentially a structure is built at steps 1, 2, ..., n which must be searched at larger heights:
$$
...
