3 ms·

I like the analogy, but the fair comparison would be comparing adding some specific piece versus subtracting some specific piece, or comparing adding some arbit

I like the analogy, but the fair comparison would be comparing adding some specific piece versus subtracting some specific piece, or comparing adding some arbitrary piece versus subtracting some arbitrary piece. For the former, you have to check your potential addition against all pieces (N checks) or your potential subtraction against all other pieces (N-1 checks). For the latter, you check all potential additions against all pieces (K x N checks) or all potential subtractions against all other pieces (N x N checks). In your comment, you're comparing checking the viability of a known addition to the entire search for a viable subtraction, ignoring the search for a viable addition.

jjk166 6y ago
really I'm just assuming K << N and constant as you can arbitrarily specify an addition but not a subtraction. Consider a nuclear power plant. While there might be an infinite number of potential safety valves I could add, it won't take me long to figure out one that will be good enough that I can safely add it somewhere without causing problems. Doubling the available valve options does not really make the task harder, but doubling the complexity does mean it takes about two times longer to validate it. On the other hand if we presuppose that there is one valve in the plant that should be removed, I will on average have to evaluate around half of all the valves before finding it. If you double the number of valves in the plant, now each evaluation is twice as hard, and I will on average have to do twice as many such evaluations, so the task should take about four times as long.
KajMagnus 6y ago
Often (but not always), finding a good enough addition is "almost instant", O(1) — for example, in software, how to implement a new feature, can come to you directly, when you read the new feature description. But to find something to delete — then one needs to know about all existing source code — that takes O(N) to read and think about. (Unless keeps it all in memory) Meaning, in practice, it's often O(1 * N), versus O(N * N). But yes you're right about the cases when it's a complex thing that can be done in many ways.

jjk166 6y ago

really I'm just assuming K << N and constant as you can arbitrarily specify an addition but not a subtraction. Consider a nuclear power plant. While there might be an infinite number of potential safety valves I could add, it won't take me long to figure out one that will be good enough that I can safely add it somewhere without causing problems. Doubling the available valve options does not really make the task harder, but doubling the complexity does mean it takes about two times longer to validate it. On the other hand if we presuppose that there is one valve in the plant that should be removed, I will on average have to evaluate around half of all the valves before finding it. If you double the number of valves in the plant, now each evaluation is twice as hard, and I will on average have to do twice as many such evaluations, so the task should take about four times as long.

KajMagnus 6y ago

Often (but not always), finding a good enough addition is "almost instant", O(1) — for example, in software, how to implement a new feature, can come to you directly, when you read the new feature description. But to find something to delete — then one needs to know about all existing source code — that takes O(N) to read and think about. (Unless keeps it all in memory) Meaning, in practice, it's often O(1 * N), versus O(N * N). But yes you're right about the cases when it's a complex thing that can be done in many ways.