Overleg:Grote-O-notatie

Wat betreft de laatste zin, is dit wel waar. Naar mijn gevoel is exacte het omgekeerdere waar (i.e. poynomiaal groeit juist langzamer dan exponetieel) en zijn polynomiale algoritme exponetieel.– De voorgaande bijdrage werd geplaatst door ? (overleg · bijdragen)

Ik heb het verbeterd. - Patrick (overleg) 7 mrt 2015 13:32 (CET)

Warrige zin

Madyno zet steeds het volgende zinsdeel terug: "als er een positief getal $M\in \mathbb {R} ,\ M>0$ en een getal $x_{0}\in \mathbb {R}$ is, zodanig dat voor $x>x_{0}$, d.w.z. voor voldoend grote $x$, geldt $|f(x)|\leq M\,|g(x)|$."

Dat is echter logisch/taalkundig min of meer gelijkwaardig met:

"als er een positief getal $M\in \mathbb {R} ,\ M>0$ en een getal $x_{0}\in \mathbb {R}$ is, zodanig dat voor $x>x_{0}$ geldt $|f(x)|\leq M\,|g(x)|$,

d.w.z.

als er een positief getal $M\in \mathbb {R} ,\ M>0$ en een getal $x_{0}\in \mathbb {R}$ is, zodanig dat voor voldoend grote $x$ geldt $|f(x)|\leq M\,|g(x)|$."

In het tweede deel is "en een getal $x_{0}\in \mathbb {R}$" onzinnig, net als wanneer je het zou vervangen door "en een broodje kaas".

Sterker nog, voor een gegeven $x_{0}\in \mathbb {R}$ is "voor $x>x_{0}$" niet gelijkwaardig met "voor voldoend grote $x$", dus er staat niet alleen iets raars, maar echt iets verkeerds. - Patrick (overleg) 5 mrt 2016 22:55 (CET)

Het punt is dat Patrick de term 'voldoend groot' heeft geïntroduceerd, op zodanige wijze dat de verwarring ontstaat. Mij gaat het er alleen om dat 'voldoend grote' als toelichting gegeven wordt, zonder de specifieke nadruk die het krijgt als het apart als uitspraak geschreven wordt. Madyno (overleg) 6 mrt 2016 10:22 (CET)

Overigens is de zin gelijkwaardig met:

als er een positief getal $M\in \mathbb {R} ,\ M>0$ zodanig dat voor voldoend grote $x$ geldt $|f(x)|\leq M\,|g(x)|$." Madyno (overleg) 6 mrt 2016 10:26 (CET)

Nee, de warrige zin zegt dat, voor een gegeven $x_{0}$, "voor $x>x_{0}$" gelijkwaardig is met "voor voldoend grote $x$", en dat klopt niet. Of een wiskundige bewering goed of fout is hangt niet af van ergens de nadruk op leggen. Soms is het zinvol een wiskundige bewering informeel toe te lichten, maar dan zeg je dat erbij; hier is dat niet aan de orde want "voldoend grote" heeft wel een exacte betekenis. - Patrick (overleg) 6 mrt 2016 11:26 (CET)

Complexiteit van de beste sorteeralgoritmen.

Dit is niet correct:

$O(n\log n)$: linearitmisch: product van de vorige twee - dit is de complexiteit van de beste sorteeralgoritmen die bekend zijn;

Er bestaan niet-comparatieve sorteeralgoritmen die mogelijks sneller zijn dan $O(n\log n)$., bijvoorbeeld Radix sort. Van comparatieve sorteeralgoritmen is het wiskundig bewezen dat deze niet beter kunnen zijn dan $O(n\log n)$. Ik zou daarom niet insinueren dat er mogelijks betere sorteeralgoritmen zijn die nog niet bekend zijn.

Op de Engelstalige Wikipedia schrijft men: fastest possible comparison sort; heapsort and merge sort. Dit klopt wel.

Wardva (overleg) 9 jan 2022 21:34 (CET)