### nor's blog

By nor, 18 months ago,
• +144

 » 18 months ago, # |   +19 orz blogCoincidence? I think not
 » 18 months ago, # |   +153 I think that your blogs produce the opposite effect of what you are trying to achieve (although my skill for understanding people is negative, so take that with a grain of salt).You make it seem that proving is something hard that is only available to people with special education in math. You insist on using the phrase "formal proof" which seems to suggest writing everything in symbols, maybe even starting proving from axioms. You mention Coq, and as a person who had a course in Coq and remembers how hard it is to prove "obvious" stuff like the commutativity of addition for integers, I can say that it is not good for supporting your position. From here I will address an imaginary flat-earther proof-denier.Mathematical proof is an argument so convincing, that you are prepared to use it to convince other people. Imagine a person who doesn't believe in your claims (imagine me). But they don't want to mess with you, they want to get convinced, they just don't want to trust your word. Can they find a hole in your arguments? If not, it is strict.It's ok to use natural language in proofs. It's ok to reuse known theorems in proofs. It's ok to cut some corners (but only after you got some experience). It's ok to say that something is obvious.It's not ok to believe in some greedy and justify it by saying "it's clear that this is the worst case and we are doing fine in it". Because there are very few situations when you can actually understand what is the worst case for your greedy.Here is the example of "your average it's the worst case logic": A decreasing array is clearly the hardest to sort in increasing order, it even has the maximum number of inversions. A decreasing array is sorted by reversing the array. Therefore, reversing the array sorts the array in $O(n)$.Ridiculous? But how is it different from this?There shouldn't be any assumptions in your proof, apart from the ones given in the statement. There are some quasi-exceptions to this, like if the problem has random input, it's ok to say that some property will hold because of randomness and then just check that it actually holds by running the code a lot of times. Or something similar. Running an exhaustive search is a valid method of proving. Running your greedy on some tests you believe to be the worst is not.Read Everule's blog and comment section. Try to come up with proofs yourself. You will get better with practice.
•  » » 18 months ago, # ^ |   +39 Very nice proof that sorting is $O(n)$
•  » » 18 months ago, # ^ |   +8 One example is this: in a game theory problem in a contest I coordinated, there was a DP to find winning and losing states. The intended constraints were such that a linear/linearithmic solution passes. However, it turned out that you could tweak the order of computing some things in a brute-force solution to get an $O(n \log n)$ algorithm, by just doing $O(n / i)$ operations for the $i$-th step.Tweaking just the order is what I call a heuristic here (it's quite simple to mindlessly guess that it will work), and often there are situations where these kinds of heuristics come up and have provably good properties.