2 citations · 2 across the 4 of their papers we have counts for
4 papers
Elementary Yet Precise Worst-case Analysis of MergeSort, A short version (SV)
Marek A. Suchenek
This paper offers two elementary yet precise derivations of an exact formula \[ W(n) = \sum_{i=1} ^{n} \lceil \lg i \rceil = n \lceil \lg n \rceil - 2^{\lceil \lg n \rceil} + 1 \]…
Best-case Analysis of MergeSort with an Application to the Sum of Digits Problem, A manuscript (MS) v2
Marek A. Suchenek
An exact formula \[ B(n) = \frac{n}{2}(\lfloor \lg n \rfloor + 1) - \sum _{k=0} ^{\lfloor \lg n \rfloor} 2^k Zigzag(\frac{n}{2^{k+1}}), \] where \[ Zigzag (x) = \min (x - \lfloor x…
A Complete Worst-Case Analysis of Heapsort with Experimental Verification of Its Results, A manuscript (MS)
Marek A. Suchenek
A rigorous proof is presented that the number of comparisons of keys performed in the worst case by on any array of size is equal to: $ 2 (N-1)\, ( \, \…
Technical Notes on Complexity of the Satisfiability Problem
Marek A. Suchenek
These notes contain, among others, a proof that the average running time of an easy solution to the satisfiability problem for propositional calculus is, under some reasonable assu…