New answers tagged algorithm-analysis
0
votes
Finding growth rate of T(n) of a code segment
Let $I$ be the number of times the for i is executed, $J$ the number of times for j, and $K$ the number of times ...
- 15k
1
vote
Accepted
Is a predecessor subgraph always connected?
Let $s$ be your source vertex and let $d(v)$ denote the distance from $s$ to $v$. Let $v_1, \dots, v_n$ be the vertices of your graph in non-decreasing order of distances from $s$.
You can show by ...
- 27.4k
0
votes
How to prove greedy algorithm is correct
It is great if you can construct cases where the optimal solution is known. In that case generate a million cases and check if they find the expected result.
Or find a mate who implements a different ...
- 27.8k
2
votes
How to prove greedy algorithm is correct
There is a very nice theory on when greedy algorithms work in general. It is based on the abstract concept of matroids. A detailed explanation is given by Jeremy Kun.
- 13.9k
2
votes
How to prove greedy algorithm is correct
Jeff Ericson in his "Algorithms" states three conditions:
Greedy choice: There is an optimal solution that includes the choice the algorithm makes.
Inductive structure: The smaller ...
- 13.9k
Top 50 recent answers are included