{"id":73,"date":"2021-12-15T09:53:15","date_gmt":"2021-12-15T09:53:15","guid":{"rendered":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/chapter\/landau-notation\/"},"modified":"2021-12-15T09:53:15","modified_gmt":"2021-12-15T09:53:15","slug":"landau-notation","status":"publish","type":"chapter","link":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/chapter\/landau-notation\/","title":{"raw":"Landau Notation","rendered":"Landau Notation"},"content":{"raw":"\n<style>.cmr-5{font-size:50%;}\n.cmr-7{font-size:70%;}\n.cmmi-5{font-size:50%;font-style: italic;}\n.cmmi-7{font-size:70%;font-style: italic;}\n.cmmi-10{font-style: italic;}\n.cmsy-5{font-size:50%;}\n.cmsy-7{font-size:70%;}\n.cmbx-10{ font-weight: bold;}\n.cmbsy-10{font-weight: bold;}\n.cmbsy-10{font-weight: bold;}\n.cmbsy-10{font-weight: bold;}\n.cmbsy-7{font-size:70%;font-weight: bold;}\n.cmbsy-7{font-weight: bold;}\n.cmbsy-7{font-weight: bold;}\n.cmbsy-5{font-size:50%;font-weight: bold;}\n.cmbsy-5{font-weight: bold;}\n.cmbsy-5{font-weight: bold;}\n.cmex-7{font-size:70%;}\n.cmex-7x-x-71{font-size:49%;}\n.msam-7{font-size:70%;}\n.msam-5{font-size:50%;}\n.msbm-7{font-size:70%;}\n.msbm-5{font-size:50%;}\n.cmr-17{font-size:170%;}\n.cmr-12{font-size:120%;}\n.cmti-10{ font-style: italic;}\np{margin-top:0;margin-bottom:0}\np.indent{text-indent:0;}\np + p{margin-top:1em;}\np + div, p + pre {margin-top:1em;}\ndiv + p, pre + p {margin-top:1em;}\n@media print {div.crosslinks {visibility:hidden;}}\na img { border-top: 0; border-left: 0; border-right: 0; }\ncenter { margin-top:1em; margin-bottom:1em; }\ntd center { margin-top:0em; margin-bottom:0em; }\n.Canvas { position:relative; }\nmath { text-indent: 0em; }\nli p.indent { text-indent: 0em }\nli p:first-child{ margin-top:0em; }\nli p:last-child, li div:last-child { margin-bottom:0.5em; }\nli p~ul:last-child, li p~ol:last-child{ margin-bottom:0.5em; }\n.enumerate1 {list-style-type:decimal;}\n.enumerate2 {list-style-type:lower-alpha;}\n.enumerate3 {list-style-type:lower-roman;}\n.enumerate4 {list-style-type:upper-alpha;}\n.obeylines-h,.obeylines-v {white-space: nowrap; }\ndiv.obeylines-v p { margin-top:0; margin-bottom:0; }\n.overline{ text-decoration:overline; }\n.overline img{ border-top: 1px solid black; }\ntd.displaylines {text-align:center; white-space:nowrap;}\n.centerline {text-align:center;}\n.rightline {text-align:right;}\npre.verbatim {font-family: monospace,monospace; text-align:left; clear:both; }\n.fbox {padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }\ndiv.fbox {display:table}\ndiv.center div.fbox {text-align:center; clear:both; padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }\ndiv.minipage{width:100%;}\ndiv.center, div.center div.center {text-align: center; margin-left:1em; margin-right:1em;}\ndiv.center {text-align: left;}\ndiv.flushright, div.flushright div.flushright {text-align: right;}\ndiv.flushright div {text-align: left;}\ndiv.flushleft {text-align: left;}\n.underline{ text-decoration:underline; }\n.underline img{ border-bottom: 1px solid black; margin-bottom:1pt; }\n.framebox-c, .framebox-l, .framebox-r { padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }\n.framebox-c {text-align:center;}\n.framebox-l {text-align:left;}\n.framebox-r {text-align:right;}\nspan.thank-mark{ vertical-align: super }\nspan.footnote-mark sup.textsuperscript, span.footnote-mark a sup.textsuperscript{ font-size:80%; }\ndiv.tabular, div.center div.tabular {text-align: center; margin-top:0.5em; margin-bottom:0.5em; }\ntable.tabular td p{margin-top:0em;}\ntable.tabular {margin-left: auto; margin-right: auto;}\ntd p:first-child{ margin-top:0em; }\ntd p:last-child{ margin-bottom:0em; }\ndiv.td00{ margin-left:0pt; margin-right:0pt; }\ndiv.td01{ margin-left:0pt; margin-right:5pt; }\ndiv.td10{ margin-left:5pt; margin-right:0pt; }\ndiv.td11{ margin-left:5pt; margin-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\ntd.td00{ padding-left:0pt; padding-right:0pt; }\ntd.td01{ padding-left:0pt; padding-right:5pt; }\ntd.td10{ padding-left:5pt; padding-right:0pt; }\ntd.td11{ padding-left:5pt; padding-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\n.hline hr, .cline hr{ height : 0px; margin:0px; }\n.hline td, .cline td{ padding: 0; }\n.hline hr, .cline hr{border:none;border-top:1px solid black;}\n.tabbing-right {text-align:right;}\ndiv.float, div.figure {margin-left: auto; margin-right: auto;}\ndiv.float img {text-align:center;}\ndiv.figure img {text-align:center;}\n.marginpar,.reversemarginpar {width:20%; float:right; text-align:left; margin-left:auto; margin-top:0.5em; font-size:85%; text-decoration:underline;}\n.marginpar p,.reversemarginpar p{margin-top:0.4em; margin-bottom:0.4em;}\n.reversemarginpar{float:left;}\n.equation td{text-align:center; vertical-align:middle; }\ntd.eq-no{ width:5%; }\ntable.equation { width:100%; }\ndiv.math-display, div.par-math-display{text-align:center;}\nmtr.hline mtd{ border-bottom:black solid 1px; padding-top:2px; padding-bottom:0em; }\nmtr.hline mtd mo{ display:none }\nmath .texttt { font-family: monospace; }\nmath .textit { font-style: italic; }\nmath .textsl { font-style: oblique; }\nmath .textsf { font-family: sans-serif; }\nmath .textbf { font-weight: bold; }\nmo.MathClass-op + mi{margin-left:0.3em}\nmi + mo.MathClass-op{margin-left:0.3em}\n math mstyle[mathvariant=\"bold\"] { font-weight: bold; font-style: normal; }\n math mstyle[mathvariant=\"normal\"] { font-weight: normal; font-style: normal; }\n.partToc a, .partToc, .likepartToc a, .likepartToc {line-height: 200%; font-weight:bold; font-size:110%;}\n.index-item, .index-subitem, .index-subsubitem {display:block}\ndiv.caption {text-indent:-2em; margin-left:3em; margin-right:1em; text-align:left;}\ndiv.caption span.id{font-weight: bold; white-space: nowrap; }\nh1.partHead{text-align: center}\np.bibitem { text-indent: -2em; margin-left: 2em; margin-top:0.6em; margin-bottom:0.6em; }\np.bibitem-p { text-indent: 0em; margin-left: 2em; margin-top:0.6em; margin-bottom:0.6em; }\n.paragraphHead, .likeparagraphHead { margin-top:2em; font-weight: bold;}\n.subparagraphHead, .likesubparagraphHead { font-weight: bold;}\n.quote {margin-bottom:0.25em; margin-top:0.25em; margin-left:1em; margin-right:1em; text-align:justify;}\n.verse{white-space:nowrap; margin-left:2em}\ndiv.maketitle {text-align:center;}\nh2.titleHead{text-align:center;}\ndiv.maketitle{ margin-bottom: 2em; }\ndiv.author, div.date {text-align:center;}\ndiv.thanks{text-align:left; margin-left:10%; font-size:85%; font-style:italic; }\ndiv.author{white-space: nowrap;}\n.quotation {margin-bottom:0.25em; margin-top:0.25em; margin-left:1em; }\n.abstract p {margin-left:5%; margin-right:5%;}\ndiv.abstract {width:100%;}\ndiv.tabular, div.center div.tabular {text-align: center; margin-top:0.5em; margin-bottom:0.5em; }\ntable.tabular td p{margin-top:0em;}\ntable.tabular {margin-left: auto; margin-right: auto;}\ntd p:first-child{ margin-top:0em; }\ntd p:last-child{ margin-bottom:0em; }\ndiv.td00{ margin-left:0pt; margin-right:0pt; }\ndiv.td01{ margin-left:0pt; margin-right:5pt; }\ndiv.td10{ margin-left:5pt; margin-right:0pt; }\ndiv.td11{ margin-left:5pt; margin-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\ntd.td00{ padding-left:0pt; padding-right:0pt; }\ntd.td01{ padding-left:0pt; padding-right:5pt; }\ntd.td10{ padding-left:5pt; padding-right:0pt; }\ntd.td11{ padding-left:5pt; padding-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\n.hline hr, .cline hr{ height : 0px; margin:0px; }\n.hline td, .cline td{ padding: 0; }\n.hline hr, .cline hr{border:none;border-top:1px solid black;}\n.equation-star td{text-align:center; vertical-align:middle; }\ntable.equation-star { width:100%; border-bottom-color: rgb(255,255,255); }\n#content table.equation-star, #content table.equation-star tbody tr td { border: 0px none rgb(255,255,255); }\nmtd.align-odd{margin-left:2em; text-align:right;}\nmtd.align-even{margin-right:2em; text-align:left;}\n.boxed{border: 1px solid black; padding-left:2px; padding-right:2px;}\n.rotatebox{display: inline-block;}\n.item-head{float:left;width:2em;clear:left;}\n.item-content{margin-left:2em;}\n .foreignobject {line-height:100%; font-size:120%; font-family:STIXgeneral,Times,Symbol,cmr10,CMSY10,CMEX10;padding:0; margin:0; text-align:center; }\nmath {vertical-align:baseline; line-height:100%; font-size:100%; font-family:STIXGeneral,Times,Symbol, cmr10,cmsy10,cmex10,cmmi10; font-style: normal; margin:0; padding:0; }\n\n.entry-title{display: none}\n\ndiv.newtheorem { margin-bottom: 2em; margin-top: 2em; border: 1px solid #333; background: #c7e4da; border-color: #4eb79e;}\ndiv.newtheorem h3 { background: #4eb79e; color: white; padding: 0px 15px 0px 15px; margin-top: 12px}\ndiv.newtheorem p { padding: 15px 15px 15px 15px; }\n\ndiv.newtheorem p span.head .ecbx-1095{font-weight: bold}\ndiv.newtheorem p .ecti-1095{font-style: italic}\ndiv.newtheorem div.custom-itemize{font-style: italic}\ndiv.quote{font-style: italic}\ndiv.newtheorem dl, dl.enumerate {display: grid; grid-template-columns: 5% auto; align-items: start; margin-top: 1em}\ndiv.newtheorem dl dd, dl.enumerate dd {margin-bottom: 0.5em}\ndiv.newtheorem dl dt, dl.enumerate dt {font-weight: normal; margin-top: 0px; text-align: right; margin-right: 15%}\ndiv.newtheorem dl dd {font-style: italic}\ndiv.newtheorem dl dt {font-style: italic}\ndiv.proof p span.ecti-1095 {font-style: italic}\ndiv.figure p img { margin-left: auto; margin-right: auto; display: block; }\ndiv.mefigcentered, div.figure { text-align: center }\n\ndl:after {content:\"\";display:table;clear:both;}\ndd {padding:.5em 0;}\ndl {width:100%;}\ndt, dd {display:inline-block; width:125%;}\ndt {text-align:right; font-weight:bold; clear:left; float:left;}\ndd {width:100%; padding-left:1em; padding-top: 0px; clear:right;}\ndd + dd {float:right; clear:both;}\ndd + dt {clear:both;}\ndt + dt {width: 100%; float: none; padding: 0 70% 0 0;}\ndt + dt + dd {margin-top: -2em;}\ndt + dt + dd + dt {margin-top: 2em;}\n<\/style>\n<style>\n\/* CSS Analysis-Skript D-Math ETHZ *\/\n\n\/* Uniform Font, also for headers *\/\nh3 {\n\tfont-family: \"Times New Roman\", serif;\n\tmargin-bottom: 35px;\n}\nh4 {\n\tfont-family: \"Times New Roman\", serif;\n}\nh5 {\n\tfont-family: \"Times New Roman\", serif;\n}\n\n\/* Bold font, e.g. for definitions *\/\n.ecbx-1095 {font-weight: 550 ;}\n\n\n\/* Uniform spacing, indent: larger, noindent, enumerate, itemize *\/\np.indent {\n\tmargin: 25px 0px 0px 0px;\n\ttext-indent: 0px; \n}\np.noindent {\n\tmargin: 15px 0px 0px 0px;\n\ttext-indent: 0px; \n}\ndl.enumerate {\n\tmargin: 0px 0px 0px 0px;\n}\ndl.enumerate dt, dl.enumerate dd {\n\tmargin-top: 15px;\n\tmargin-bottom: 0px;\n}\ndiv.custom-itemize {\n\tmargin: 0px 0px 0px 0px;\n}\ndiv.custom-itemize div.item-head {\n\tmargin-top: 15px;\n\tmargin-bottom: 0px;\n\ttext-align: center;\n}\ndiv.custom-itemize div.item-head:first-of-type {\n\tmargin-top: 0px;\n} \ndiv.custom-itemize div.item-content {\n\tmargin-top: 15px;\n\tmargin-bottom: 0px;\n}\n.MJXc-display {\n\tmargin: 15px 0px 0px 0px;\n}\n\n\n\n\/* green metheorem\/melemma CSS class for more\/medium important latex-theorem-environments *\/\n\/* metheorem box+header *\/\ndiv.metheorem {\n    margin-bottom: 40px;\n    margin-top: 40px;\n\tpadding: 0px 15px 15px 15px;\n    border: 1px solid #333;\n    border-color: #4eb79e;\n    background: #c7e4da;\n}\ndiv.metheorem h4 {\n    background: #4eb79e;\n    color: white;\n\tmargin-top: 12px;\n\tmargin-left: -15px;\n\tmargin-right: -15px;\n\tpadding: 0px 15px 0px 15px;\n}\n\/* melemma box+header *\/\ndiv.melemma {\n    margin-bottom: 40px;\n    margin-top: 40px;\n\tpadding: 0px 15px 15px 15px;\n    border: 1px solid #333;\n    border-color: #4eb79e;\n    background: #F2F2F2;\n}\ndiv.melemma h4 {\n    background: #4eb79e;\n    color: white;\n\tmargin-top: 12px;\n\tmargin-left: -15px;\n\tmargin-right: -15px;\n\tpadding: 0px 15px 0px 15px;\n}\n\/* meexample box+header *\/\ndiv.meexample {\n    margin-bottom: 30px;\n    margin-top: 30px;\n\tpadding: 0px 15px 15px 15px;\n\tborder-color: gainsboro;\n\tborder-style: solid;\n\tborder-width: thin;\n}\ndiv.meexample h4 {\n\tfont-size: inherit;\n\tfont-weight: bold;\n    padding: 15px 0px 0px 0px;\n\tmargin-top: 0px;\n\tmargin-bottom: 5px;\n}\ndiv.meexample h4+p.noindent, div.meexample h4+p.indent {\n\tmargin-top: 5px;\n\ttext-indent: 0px;\n}\n\/* padding and margins for stuff inside these boxes, CSS-selector &gt; doesn't work in WP *\/\ndiv.me details {\n\tmargin: 10px 0px 0px 0px;\n}\ndiv.me dd {\n    width: calc(100% - 30px);\n}\t\n\n\n\/* fixing background of pictures *\/\nimg {\n\tbackground: white;\n}\n\n\/* div-container for centered geoapplet *\/\ndiv.geoapplet {\n\tmargin-left: auto;\n\tmargin-right: auto;\n\tmargin-top: 15px;\n\tmax-width: 100%;\n}\ndiv.geoapplet iframe {\n\tborder-style: none;\n\tmax-height: 110vw;\n}\n\n\/* div-container for centered squeezed tables *\/\ndiv.websqueeze {\n\tmargin-left: auto;\n\tmargin-right: auto;\n}\n\n\/* two containers for squeezing text sizes *\/\ndiv.mesmalltext, div.mesmalltext * {\n\tfont-size: 15px;\n}\nspan.metinytext, span.metinytext * {\n\tfont-size: 12px;\n}\n\n\n\/* removing grid lines in equations *\/\n#content table.equation tr td, #content table.equation tr th {\n    border: none;\n}\n#content table.equation {\n    border: none;\n}\n\n\/* hover\/click-solution for short inline explanations and footnotes *\/\n.hover-text {    \/* hidden part *\/\n    display: none;\n}\n.marginpar {     \/* style for footnote as marginpar *\/\n\ttext-decoration: none;\n\tborder: solid;\n\tborder-width: 1pt;\n\tpadding: 3pt;\t\n\twidth: 30%;\n\tbackground: white;\n}\n.hover-trigger { \/* style for hover\/click-trigger text\/symbol *\/\n\tbackground: none;\n\tborder: none;\n\tpadding: 0;\n\toutline: inherit;\t\n\ttext-transform: none;\n\tfont: inherit;\n\tposition: inherit;\n\tvertical-align: baseline;\n    color: #FF7F00;\n\tcursor: help;\n}\n.hover-trigger:hover +.hover-text{\n    display: inline;\n}\n.hover-trigger:active +.hover-text{\n    display: inline;\n}\n\n\/* simplifying style of details\/summary, removing triangle *\/\ndetails summary {\n  background: none;\n  list-style: none;\n  outline: none;\n  cursor: pointer;\n}\ndetails summary::-webkit-details-marker { \n  display: inline;\n  display: none;\n}\n\n\/* MC-True\/False as inline details\/summary *\/\ndetails.mcquest, div.me details.mcquest {\n\tdisplay: inline;\n\tmargin-top: 0px;\n}\nsummary.mcquest {\n\tdisplay: inline;\n\tcolor: #FF7F00;\n\tcursor: help;\n}\n\n\/* proof style: simple black box with gray background \n                little black square at the end on the right *\/\ndiv.proof {\n\tborder-color: black;\n\tborder-style: solid;\n\tborder-width: thin;\n\tbackground-color: #F2F2F2;\n\tpadding: 15px;\n\tmargin-top: 1em; \n}\ndiv.proof p:first-of-type {\n\tmargin: 0px;\n}\ndiv.qed {\n\tmargin-top: -25px;\n\tmargin-bottom: -7px;\n\ttext-align: right;\n}\ntable.equation+div.qed {\n\tmargin-top: -65px;\n}\n\n\/* The following is making also math-formulas inside the headers of Lemmas, etc., white. *\/\ndiv.melemma h4 span {\n    color: white;\n}\ndiv.metheorem h4 span {\n    color: white;\n}\n\n\/* The following are used to avoid fullstop, period, colon, semicolon, and endquote (broader) to move by itself to the next line after a formula.\n   The math-environment before needs to be wrapped in span.maperiod and the fullstop etc. in a span.period --- together they achieve what we want.  *\/\nspan.maperiod {\n       margin-right: 5px;\n}\nspan.period {\n       display: inline-block;\n       width: 0px;\n       margin-left: -5px;\n       margin-right: 4.9px;\n\t   text-indent: 0px;\n}\nspan.maendquote {\n       margin-right: 8px;\n}\nspan.endquote {\n       display: inline-block;\n       width: 0px;\n       margin-left: -8px;\n       margin-right: 7.9px;\n}\n\n\n\/* The following is removing an extra space left of the equation side in aligned equations *\/\nspan.mjx-mtd {\n    padding-left: 0em !important;\n}\n\n\/* The following fixes the weird problem that math appears smaller if it was rendered while the details tag was closed. *\/\ndetails span.mjx-chtml, details span.MathJax_CHTML {\n font-size: 100% !important;\n}\n\n\/* trying to fix line breaks in verbatim, new lines are missing *\/\npre.verbatim {\n\twhite-space: pre-wrap;\n\tfont-size: small;\n}\n<\/style><h3 id=\"z45ab6594496c\" class=\"sectionHead\"><span class=\"titlemark\">6.6 <\/span> <a id=\"x1-1820006\"><\/a>Landau Notation<\/h3> <p class=\"noindent\">Wir f\u00fchren nun zwei gel\u00e4ufige Notationen ein, die das asymptotische Verhalten einer Funktion mit dem asymptotischen Verhalten einer anderen Funktion vergleichen \u2013 also ein relatives asymptotisches Verhalten beschreiben. <\/p><p class=\"indent\">Sei <math display=\"inline\"><mi>D<\/mi> <mo class=\"MathClass-rel\">\u2286<\/mo> <mi>\u211d<\/mi><\/math> eine Teilmenge und <math display=\"inline\"><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <mo class=\"MathClass-rel\">\u2208<\/mo> <mover accent=\"false\" class=\"mml-overline\"><mrow><mi>\u211d<\/mi> <\/mrow><mo accent=\"true\">\u00af<\/mo><\/mover> <\/math> ein H\u00e4ufungspunkt (also mit <math display=\"inline\"><msub><mrow><mover accent=\"true\"><mrow><mi>U<\/mi><\/mrow><mo accent=\"true\">\u02d9<\/mo><\/mover><\/mrow><mrow><mi>\u03b4<\/mi><\/mrow><\/msub> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow> <mo class=\"MathClass-bin\">\u2229<\/mo> <mi>D<\/mi><mo class=\"MathClass-rel\">\u2260<\/mo><mi>\u2205<\/mi><\/math> f\u00fcr alle <math display=\"inline\"><mi>\u03b4<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math>). Seien <math display=\"inline\"><mi>f<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>g<\/mi> <mo class=\"MathClass-punc\">:<\/mo> <mi>D<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <mi>\u211d<\/mi><\/math> Funktionen. Wir schreiben <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><mo class=\"MathClass-punc\">,<\/mo><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\">falls ein <math display=\"inline\"><mi>\u03b4<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math> und eine Konstante <math display=\"inline\"><mi>M<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math> existieren, so dass <math display=\"inline\"><mo class=\"MathClass-rel\">|<\/mo><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-rel\">|<\/mo><mo class=\"MathClass-rel\">\u2264<\/mo> <mi>M<\/mi><mo class=\"MathClass-rel\">|<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-rel\">|<\/mo><\/math> f\u00fcr alle <span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>D<\/mi> <mo class=\"MathClass-bin\">\u2229<\/mo><msub><mrow><mover accent=\"true\"><mrow><mi>U<\/mi><\/mrow><mo accent=\"true\">\u02d9<\/mo><\/mover><\/mrow><mrow><mi>\u03b4<\/mi><\/mrow><\/msub> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math><\/span><span class=\"period\">.<\/span> In anderen Worten, <math display=\"inline\"><mi>f<\/mi><\/math> ist \u201e <span class=\"ecbx-1095\">Gross-O<\/span>\u201c  von <math display=\"inline\"><mi>g<\/mi><\/math> f\u00fcr&nbsp;<span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math><\/span><span class=\"period\">,<\/span> falls in einer punktierten Umgebung von&nbsp;<math display=\"inline\"><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math> die Funktion <math display=\"inline\"><mi>f<\/mi><\/math> durch eine Konstante mal <math display=\"inline\"><mo class=\"MathClass-rel\">|<\/mo><mi>g<\/mi><mo class=\"MathClass-rel\">|<\/mo><\/math> beschr\u00e4nkt werden kann. Obwohl dies f\u00fcr obige Defintion nicht notwendig ist, werden wir eigentlich immer vorraussetzen, dass <math display=\"inline\"><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-rel\">\u2260<\/mo><mn>0<\/mn><\/math> f\u00fcr alle <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>D<\/mi><\/math> oder zumindest f\u00fcr alle <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo><msub><mrow><mover accent=\"true\"><mrow><mi>U<\/mi><\/mrow><mo accent=\"true\">\u02d9<\/mo><\/mover><\/mrow><mrow><msub><mrow><mi>\u03b4<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mrow><\/msub> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math> f\u00fcr ein <span class=\"maperiod\"><math display=\"inline\"><msub><mrow><mi>\u03b4<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math><\/span><span class=\"period\">.<\/span> In diesem Fall ist <math display=\"inline\"><mi>f<\/mi><\/math> genau dann Gross-O von <span class=\"maperiod\"><math display=\"inline\"><mi>g<\/mi><\/math><\/span><span class=\"period\">,<\/span>                                                                                                                                                                           wenn <math display=\"inline\"><mfrac><mrow><mi>f<\/mi><\/mrow> <mrow><mi>g<\/mi><\/mrow><\/mfrac><\/math> in einer <math display=\"inline\"><mi>\u03b4<\/mi><\/math>-Umgebung von <math display=\"inline\"><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <\/math> beschr\u00e4nkt ist. Nochmals in anderen Worten ist <math display=\"inline\"><mi>f<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> gleichbedeutend damit, dass <math display=\"inline\"><mi>f<\/mi><\/math> nicht viel gr\u00f6sser als <math display=\"inline\"><mi>g<\/mi><\/math> ist wenn <math display=\"inline\"><mi>x<\/mi><\/math> in der N\u00e4he von <math display=\"inline\"><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math> liegt. Zum Beispiel gilt <\/p> <div class=\"custom-itemize\"><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><math display=\"inline\"><mfrac><mrow><mi>x<\/mi><\/mrow> <mrow><mi>x<\/mi><mo class=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/mfrac> <mo class=\"MathClass-rel\">=<\/mo> <mi>O<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mn>1<\/mn><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math> f\u00fcr <span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><\/math><\/span><span class=\"period\">,<\/span> <\/div><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\">f\u00fcr jedes <math display=\"inline\"><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u211d<\/mi><\/math> gilt <math display=\"inline\"><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <mo class=\"MathClass-rel\">=<\/mo> <mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math><\/span><span class=\"period\">,<\/span> und insbesondere auch <\/div><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><math display=\"inline\"><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <mo class=\"MathClass-rel\">=<\/mo> <mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <mn>0<\/mn><\/math><\/span><span class=\"period\">,<\/span> aber <\/div><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><math display=\"inline\"><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <\/math> ist nicht gleich <math display=\"inline\"><mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><\/math> da <math display=\"inline\"><mfrac><mrow><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <\/mrow> <mrow><mi>x<\/mi><\/mrow><\/mfrac> <mo class=\"MathClass-rel\">=<\/mo> <mi>x<\/mi><\/math> in keiner Umgebung von <math display=\"inline\"><mi>\u221e<\/mi><\/math> beschr\u00e4nkt ist.<\/div><\/div> <p class=\"noindent\">Der Vorteil der Notation ist, dass wir den Namen (oben <math display=\"inline\"><mi>M<\/mi><\/math>) f\u00fcr die obere Schranke nicht einf\u00fchren. Falls uns diese Konstante nicht besonders interessiert, dann k\u00f6nnen wir uns dadurch bei Rechnungen von einer Zeile zur n\u00e4chsten auf das Wesentlich konzentrieren. Man spricht in diesem Zusammenhang auch von der <span class=\"ecbx-1095\">impliziten Konstante<\/span>, falls diese nach einigen Rechenschritten doch erw\u00e4hnt werden muss. <\/p><p class=\"indent\">Wenn <math display=\"inline\"><mi>f<\/mi><\/math> nicht nur durch <math display=\"inline\"><mi>g<\/mi><\/math> beschr\u00e4nkt ist, sondern asymptotisch gegen\u00fcber <math display=\"inline\"><mi>g<\/mi><\/math> vernachl\u00e4ssigbar ist, dann sagen wir, dass <math display=\"inline\"><mi>f<\/mi><\/math> \u201e<span class=\"ecbx-1095\">Klein-o<\/span>\u201c von <math display=\"inline\"><mi>g<\/mi><\/math> ist f\u00fcr&nbsp;<span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math><\/span><span class=\"period\">.<\/span>                                                                                                                                                                           Genauer formuliert: Wir schreiben <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><mo class=\"MathClass-punc\">,<\/mo><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\">falls f\u00fcr jedes <math display=\"inline\"><mi>\ud835\udf00<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math> ein <math display=\"inline\"><mi>\u03b4<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math> existiert mit <math display=\"inline\"><mo class=\"MathClass-rel\">|<\/mo><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-rel\">|<\/mo> <mo class=\"MathClass-rel\">\u2264<\/mo> <mi>\ud835\udf00<\/mi><mo class=\"MathClass-rel\">|<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-rel\">|<\/mo><\/math> f\u00fcr alle <span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>D<\/mi> <mo class=\"MathClass-bin\">\u2229<\/mo><msub><mrow> <mover accent=\"true\"><mrow><mi>U<\/mi><\/mrow><mo accent=\"true\">\u02d9<\/mo><\/mover> <\/mrow><mrow><mi>\u03b4<\/mi><\/mrow><\/msub> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math><\/span><span class=\"period\">.<\/span> Wie zuvor wollen wir meist&nbsp;<math display=\"inline\"><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-rel\">\u2260<\/mo><mn>0<\/mn><\/math> auf&nbsp;<math display=\"inline\"><mi>D<\/mi><\/math> annehmen. In diesem Fall gilt <math display=\"inline\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <\/math> genau dann, wenn <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><munder class=\"msub\"><mrow><mi class=\"qopname\"> lim<\/mi><mo>  <\/mo><\/mrow><mrow><mi>x<\/mi><mo class=\"MathClass-rel\">\u2192<\/mo><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mrow><\/munder><mfrac><mrow><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/mrow> <mrow><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/mrow><\/mfrac> <mo class=\"MathClass-rel\">=<\/mo> <mn>0<\/mn><mo class=\"MathClass-punc\">.<\/mo><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\">Man beachte, dass, falls die eigentlichen Grenzwerte <math display=\"inline\"><munder class=\"msub\"><mrow><mi class=\"qopname\">lim<\/mi><mo>  <\/mo><\/mrow><mrow><mi>x<\/mi><mo class=\"MathClass-rel\">\u2192<\/mo><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub><\/mrow><\/munder><mi>f<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math> und <math display=\"inline\"><munder class=\"msub\"><mrow><mi class=\"qopname\">lim<\/mi><mo>  <\/mo><\/mrow><mrow><mi>x<\/mi><mo class=\"MathClass-rel\">\u2192<\/mo><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub><\/mrow><\/munder><mi>g<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi> <\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math> existieren und nicht Null sind, sicherlich <math display=\"inline\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <\/math> erf\u00fcllt ist, aber die st\u00e4rkere Aussage <math display=\"inline\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <\/math>                                                                                                                                                                           falsch ist. Beide Notationen sind also vor allem dann interessant, wenn die Grenzwerte entweder null oder unendlich sind. Zum Beispiel gilt <\/p> <div class=\"custom-itemize\"><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><\/math> (aber nicht umgekehrt) und <\/div><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><math display=\"inline\"><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <mn>0<\/mn><\/math> (aber nicht umgekehrt).<\/div><\/div> <p class=\"indent\">Diese Notationen machen analog Sinn f\u00fcr andere Bewegungen wie zum Beispiel&nbsp;<span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2198<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math><\/span><span class=\"period\">,<\/span> allgemeine Filter, und k\u00f6nnen insbesondere auch f\u00fcr Folgen verwendet werden. <\/p> <div class=\"me meexample\"> <p class=\"indent\"><\/p><h4 id=\"z3a0314f82193\"> <a id=\"x1-182001r52\"><\/a> <span class=\"ecbx-1095\">\u00dc<\/span><span class=\"ecbx-1095\">bung 6.52 <\/span>(Klein-o Asymptotiken)<span class=\"ecbx-1095\">.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Zeigen Sie, dass die Asymptotiken<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\" \/> <mtd class=\"align-even\"><msup><mrow><mi>x<\/mi><\/mrow><mrow><mi>p<\/mi><\/mrow><\/msup> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <mn>0<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"qquad\" width=\"2em\" \/><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-odd\" columnalign=\"right\"><mi>x<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><msup><mrow><mi>x<\/mi><\/mrow><mrow><mi>p<\/mi><\/mrow><\/msup><mo class=\"MathClass-close\">)<\/mo><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><mtr><mtd class=\"align-odd\" columnalign=\"right\" \/> <mtd class=\"align-even\"><msup><mrow><mi>x<\/mi><\/mrow><mrow><mi>a<\/mi><\/mrow><\/msup> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><msup><mrow><mi>e<\/mi><\/mrow><mrow><mi>x<\/mi><\/mrow><\/msup><mo class=\"MathClass-close\">)<\/mo><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"qquad\" width=\"2em\" \/><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-odd\" columnalign=\"right\"><mi class=\"qopname\">log<\/mi><mo>  <\/mo><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><msup><mrow><mi>x<\/mi><\/mrow><mrow><mi>b<\/mi><\/mrow><\/msup><mo class=\"MathClass-close\">)<\/mo><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\"><span class=\"ecti-1095\">f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r jedes <\/span><span class=\"maperiod\"><math display=\"inline\"><mi>p<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>1<\/mn><\/math><\/span><span class=\"period\">,<\/span> <math display=\"inline\"><mi>a<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u211d<\/mi><\/math> <span class=\"ecti-1095\">und<\/span> <math display=\"inline\"><mi>b<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math> <span class=\"ecti-1095\">zutreffen, wobei sie <\/span><span class=\"ecti-1095\">\u00dc<\/span><span class=\"ecti-1095\">bung <\/span><a href=\"..\/..\/chapter\/die-exponentialfunktion#x1-173005r35\"><span class=\"ecti-1095\">6.35<\/span><\/a> <span class=\"ecti-1095\">verwenden d<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">rfen.<\/span> <\/p> <\/div> <div class=\"me meexample\"> <p class=\"indent\"><\/p><h4 id=\"zcdf36be99637\"> <a id=\"x1-182002r53\"><\/a> <span class=\"ecbx-1095\">\u00dc<\/span><span class=\"ecbx-1095\">bung 6.53 <\/span>(Rechnen mit der Landau Notation)<span class=\"ecbx-1095\">.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Seien <\/span><math display=\"inline\"><mi>D<\/mi><mo class=\"MathClass-punc\">,<\/mo><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math> <span class=\"ecti-1095\">wie oben<\/span> <span class=\"ecti-1095\">und <\/span><math display=\"inline\"><mi>f<\/mi><mo class=\"MathClass-punc\">,<\/mo> <msub><mrow><mi>f<\/mi><\/mrow><mrow><mn>1<\/mn> <\/mrow> <\/msub> <mo class=\"MathClass-punc\">,<\/mo> <msub><mrow><mi>f<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msub><mo class=\"MathClass-punc\">,<\/mo><mi>g<\/mi><\/math> <span class=\"ecti-1095\">reellwertige<\/span> <span class=\"ecti-1095\">Funktionen auf <\/span><span class=\"maperiod\"><math display=\"inline\"><mi>D<\/mi><\/math><\/span><span class=\"period\">.<\/span> <span class=\"ecti-1095\">Zeigen Sie, dass falls <\/span><math display=\"inline\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><msub><mrow><mi>f<\/mi><\/mrow><mrow><mn>1<\/mn><\/mrow><\/msub><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">und <\/span><math display=\"inline\"><mspace class=\"nbsp\" width=\"0.33em\" \/><msub><mrow><mi>f<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msub> <mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r <\/span><span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <\/math><\/span><span class=\"period\">,<\/span> <span class=\"ecti-1095\">dann auch<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><msub><mrow><mi>f<\/mi><\/mrow><mrow><mn>1<\/mn><\/mrow><\/msub><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-bin\">+<\/mo> <msub><mrow><mi>f<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msub><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/mtd> <mtd class=\"align-even\"> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><mo class=\"MathClass-punc\">,<\/mo><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"> <mspace width=\"2em\" \/><\/mtd><\/mtr><mtr><mtd class=\"align-odd\" columnalign=\"right\"><mi>\u03b1<\/mi><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/mtd> <mtd class=\"align-even\"> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"> <mspace width=\"2em\" \/><\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\"><span class=\"ecti-1095\">f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r <\/span><math display=\"inline\"><mi>\u03b1<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u211d<\/mi><\/math> <span class=\"ecti-1095\">und analog f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r Gross-O.<\/span> <\/p> <\/div> <p class=\"indent\">Die Landau Notation wird in vielen Situationen auch als Platzhalter verwendet, um beispielsweise auszudr\u00fccken, dass ein Term in einer Summe schneller anw\u00e4chst oder abf\u00e4llt als die anderen. In einem Ausdruck der Form                                                                                                                                                                           <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-bin\">+<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\">steht der Term <math display=\"inline\"><mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr eine implizite Funktion <math display=\"inline\"><mi>h<\/mi> <mo class=\"MathClass-punc\">:<\/mo> <mi>D<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <mi>\u211d<\/mi><\/math> mit der Eigenschaft <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mi>h<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><mo class=\"MathClass-punc\">,<\/mo><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\">also soll <math display=\"inline\"><mover accent=\"true\"><mrow><mi>f<\/mi><\/mrow><mo accent=\"true\">~<\/mo><\/mover> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow> <mo class=\"MathClass-rel\">=<\/mo> <mi>f<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow> <mo class=\"MathClass-bin\">+<\/mo> <mi>o<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>g<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math> die Asymptotik <math display=\"inline\"><mover accent=\"true\"><mrow><mi>f<\/mi><\/mrow><mo accent=\"true\">~<\/mo><\/mover> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>f<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow> <mo class=\"MathClass-rel\">=<\/mo> <mi>h<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>g<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <\/math> erf\u00fcllen. Dies gilt analog ebenso f\u00fcr die Gross-O Notation. <\/p><p class=\"indent\">Beispielsweise schreibt man (nach Polynomdivision mit Rest) <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mfrac><mrow><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>3<\/mn><\/mrow><\/msup> <mo class=\"MathClass-bin\">\u2212<\/mo> <mn>7<\/mn><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msup> <mo class=\"MathClass-bin\">+<\/mo> <mn>6<\/mn><mi>x<\/mi> <mo class=\"MathClass-bin\">+<\/mo> <mn>2<\/mn><\/mrow> <mrow><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msup> <mo class=\"MathClass-bin\">+<\/mo> <mi>x<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mn>3<\/mn><mn>4<\/mn><\/mrow><\/mfrac> <\/mtd> <mtd class=\"align-even\"> <mo class=\"MathClass-rel\">=<\/mo> <mi>x<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mn>8<\/mn> <mo class=\"MathClass-bin\">+<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"> <mspace width=\"2em\" \/><\/mtd><\/mtr><mtr><mtd class=\"align-odd\" columnalign=\"right\" \/> <mtd class=\"align-even\"> <mo class=\"MathClass-rel\">=<\/mo> <mi>x<\/mi> <mo class=\"MathClass-bin\">+<\/mo> <mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"> <mspace width=\"2em\" \/><\/mtd><\/mtr><mtr><mtd class=\"align-odd\" columnalign=\"right\" \/> <mtd class=\"align-even\"> <mo class=\"MathClass-rel\">=<\/mo> <mi>x<\/mi> <mo class=\"MathClass-bin\">+<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><mo class=\"MathClass-punc\">,<\/mo><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"> <mspace width=\"2em\" \/><\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\">und erinnert sich auf der rechten Seite somit nur an jene Terme, die den Hauptteil der Bewegung <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <mi>\u221e<\/mi><\/math> ausmacht. Es mag vielleicht \u00fcberraschen, dass im obigen Beispiel alle drei Formeln zutreffen oder n\u00fctzlich sein k\u00f6nnten. Doch folgen diese Behauptungen direkt aus der Polynomdivision und je nach Zusammenhang will man vielleicht die etwas genauere Aussage mit Fehler <math display=\"inline\"><mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo><\/math> oder die gr\u00f6bere Aussage mit Hilfe des Fehlers <math display=\"inline\"><mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> verwenden. <\/p><p class=\"indent\">Derartige asymptotische Aussagen helfen in komplizierteren Argumenten und Berechnungen den Fokus auf die wesentlichen Teile einer Berechnungen zu lenken. Doch liegen in diesem Verstecken von gewissen Ausdr\u00fccken auch Risiken f\u00fcr Fehler, zum Beispiel wenn wir die Fehlerterme unbeschr\u00e4nkt oft addieren wollen oder die Fehlerterme von weiteren Parametern abh\u00e4ngen und diese Abh\u00e4ngigkeit auf Grund der Notation vergessen wird. Wir werden die Landau Notation sporadisch aber doch immer wieder einmal einsetzen um das Wesentliche an einer Aussage zu betonen.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               <a id=\"x1-182003r182\"><\/a> <\/p> \n","rendered":"\n<style scoped=\"scoped\">.cmr-5{font-size:50%;}\n.cmr-7{font-size:70%;}\n.cmmi-5{font-size:50%;font-style: italic;}\n.cmmi-7{font-size:70%;font-style: italic;}\n.cmmi-10{font-style: italic;}\n.cmsy-5{font-size:50%;}\n.cmsy-7{font-size:70%;}\n.cmbx-10{ font-weight: bold;}\n.cmbsy-10{font-weight: bold;}\n.cmbsy-10{font-weight: bold;}\n.cmbsy-10{font-weight: bold;}\n.cmbsy-7{font-size:70%;font-weight: bold;}\n.cmbsy-7{font-weight: bold;}\n.cmbsy-7{font-weight: bold;}\n.cmbsy-5{font-size:50%;font-weight: bold;}\n.cmbsy-5{font-weight: bold;}\n.cmbsy-5{font-weight: bold;}\n.cmex-7{font-size:70%;}\n.cmex-7x-x-71{font-size:49%;}\n.msam-7{font-size:70%;}\n.msam-5{font-size:50%;}\n.msbm-7{font-size:70%;}\n.msbm-5{font-size:50%;}\n.cmr-17{font-size:170%;}\n.cmr-12{font-size:120%;}\n.cmti-10{ font-style: italic;}\np{margin-top:0;margin-bottom:0}\np.indent{text-indent:0;}\np + p{margin-top:1em;}\np + div, p + pre {margin-top:1em;}\ndiv + p, pre + p {margin-top:1em;}\n@media print {div.crosslinks {visibility:hidden;}}\na img { border-top: 0; border-left: 0; border-right: 0; }\ncenter { margin-top:1em; margin-bottom:1em; }\ntd center { margin-top:0em; margin-bottom:0em; }\n.Canvas { position:relative; }\nmath { text-indent: 0em; }\nli p.indent { text-indent: 0em }\nli p:first-child{ margin-top:0em; }\nli p:last-child, li div:last-child { margin-bottom:0.5em; }\nli p~ul:last-child, li p~ol:last-child{ margin-bottom:0.5em; }\n.enumerate1 {list-style-type:decimal;}\n.enumerate2 {list-style-type:lower-alpha;}\n.enumerate3 {list-style-type:lower-roman;}\n.enumerate4 {list-style-type:upper-alpha;}\n.obeylines-h,.obeylines-v {white-space: nowrap; }\ndiv.obeylines-v p { margin-top:0; margin-bottom:0; }\n.overline{ text-decoration:overline; }\n.overline img{ border-top: 1px solid black; }\ntd.displaylines {text-align:center; white-space:nowrap;}\n.centerline {text-align:center;}\n.rightline {text-align:right;}\npre.verbatim {font-family: monospace,monospace; text-align:left; clear:both; }\n.fbox {padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }\ndiv.fbox {display:table}\ndiv.center div.fbox {text-align:center; clear:both; padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }\ndiv.minipage{width:100%;}\ndiv.center, div.center div.center {text-align: center; margin-left:1em; margin-right:1em;}\ndiv.center {text-align: left;}\ndiv.flushright, div.flushright div.flushright {text-align: right;}\ndiv.flushright div {text-align: left;}\ndiv.flushleft {text-align: left;}\n.underline{ text-decoration:underline; }\n.underline img{ border-bottom: 1px solid black; margin-bottom:1pt; }\n.framebox-c, .framebox-l, .framebox-r { padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }\n.framebox-c {text-align:center;}\n.framebox-l {text-align:left;}\n.framebox-r {text-align:right;}\nspan.thank-mark{ vertical-align: super }\nspan.footnote-mark sup.textsuperscript, span.footnote-mark a sup.textsuperscript{ font-size:80%; }\ndiv.tabular, div.center div.tabular {text-align: center; margin-top:0.5em; margin-bottom:0.5em; }\ntable.tabular td p{margin-top:0em;}\ntable.tabular {margin-left: auto; margin-right: auto;}\ntd p:first-child{ margin-top:0em; }\ntd p:last-child{ margin-bottom:0em; }\ndiv.td00{ margin-left:0pt; margin-right:0pt; }\ndiv.td01{ margin-left:0pt; margin-right:5pt; }\ndiv.td10{ margin-left:5pt; margin-right:0pt; }\ndiv.td11{ margin-left:5pt; margin-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\ntd.td00{ padding-left:0pt; padding-right:0pt; }\ntd.td01{ padding-left:0pt; padding-right:5pt; }\ntd.td10{ padding-left:5pt; padding-right:0pt; }\ntd.td11{ padding-left:5pt; padding-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\n.hline hr, .cline hr{ height : 0px; margin:0px; }\n.hline td, .cline td{ padding: 0; }\n.hline hr, .cline hr{border:none;border-top:1px solid black;}\n.tabbing-right {text-align:right;}\ndiv.float, div.figure {margin-left: auto; margin-right: auto;}\ndiv.float img {text-align:center;}\ndiv.figure img {text-align:center;}\n.marginpar,.reversemarginpar {width:20%; float:right; text-align:left; margin-left:auto; margin-top:0.5em; font-size:85%; text-decoration:underline;}\n.marginpar p,.reversemarginpar p{margin-top:0.4em; margin-bottom:0.4em;}\n.reversemarginpar{float:left;}\n.equation td{text-align:center; vertical-align:middle; }\ntd.eq-no{ width:5%; }\ntable.equation { width:100%; }\ndiv.math-display, div.par-math-display{text-align:center;}\nmtr.hline mtd{ border-bottom:black solid 1px; padding-top:2px; padding-bottom:0em; }\nmtr.hline mtd mo{ display:none }\nmath .texttt { font-family: monospace; }\nmath .textit { font-style: italic; }\nmath .textsl { font-style: oblique; }\nmath .textsf { font-family: sans-serif; }\nmath .textbf { font-weight: bold; }\nmo.MathClass-op + mi{margin-left:0.3em}\nmi + mo.MathClass-op{margin-left:0.3em}\n math mstyle[mathvariant=\"bold\"] { font-weight: bold; font-style: normal; }\n math mstyle[mathvariant=\"normal\"] { font-weight: normal; font-style: normal; }\n.partToc a, .partToc, .likepartToc a, .likepartToc {line-height: 200%; font-weight:bold; font-size:110%;}\n.index-item, .index-subitem, .index-subsubitem {display:block}\ndiv.caption {text-indent:-2em; margin-left:3em; margin-right:1em; text-align:left;}\ndiv.caption span.id{font-weight: bold; white-space: nowrap; }\nh1.partHead{text-align: center}\np.bibitem { text-indent: -2em; margin-left: 2em; margin-top:0.6em; margin-bottom:0.6em; }\np.bibitem-p { text-indent: 0em; margin-left: 2em; margin-top:0.6em; margin-bottom:0.6em; }\n.paragraphHead, .likeparagraphHead { margin-top:2em; font-weight: bold;}\n.subparagraphHead, .likesubparagraphHead { font-weight: bold;}\n.quote {margin-bottom:0.25em; margin-top:0.25em; margin-left:1em; margin-right:1em; text-align:justify;}\n.verse{white-space:nowrap; margin-left:2em}\ndiv.maketitle {text-align:center;}\nh2.titleHead{text-align:center;}\ndiv.maketitle{ margin-bottom: 2em; }\ndiv.author, div.date {text-align:center;}\ndiv.thanks{text-align:left; margin-left:10%; font-size:85%; font-style:italic; }\ndiv.author{white-space: nowrap;}\n.quotation {margin-bottom:0.25em; margin-top:0.25em; margin-left:1em; }\n.abstract p {margin-left:5%; margin-right:5%;}\ndiv.abstract {width:100%;}\ndiv.tabular, div.center div.tabular {text-align: center; margin-top:0.5em; margin-bottom:0.5em; }\ntable.tabular td p{margin-top:0em;}\ntable.tabular {margin-left: auto; margin-right: auto;}\ntd p:first-child{ margin-top:0em; }\ntd p:last-child{ margin-bottom:0em; }\ndiv.td00{ margin-left:0pt; margin-right:0pt; }\ndiv.td01{ margin-left:0pt; margin-right:5pt; }\ndiv.td10{ margin-left:5pt; margin-right:0pt; }\ndiv.td11{ margin-left:5pt; margin-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\ntd.td00{ padding-left:0pt; padding-right:0pt; }\ntd.td01{ padding-left:0pt; padding-right:5pt; }\ntd.td10{ padding-left:5pt; padding-right:0pt; }\ntd.td11{ padding-left:5pt; padding-right:5pt; }\ntable[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }\n.hline hr, .cline hr{ height : 0px; margin:0px; }\n.hline td, .cline td{ padding: 0; }\n.hline hr, .cline hr{border:none;border-top:1px solid black;}\n.equation-star td{text-align:center; vertical-align:middle; }\ntable.equation-star { width:100%; border-bottom-color: rgb(255,255,255); }\n#content table.equation-star, #content table.equation-star tbody tr td { border: 0px none rgb(255,255,255); }\nmtd.align-odd{margin-left:2em; text-align:right;}\nmtd.align-even{margin-right:2em; text-align:left;}\n.boxed{border: 1px solid black; padding-left:2px; padding-right:2px;}\n.rotatebox{display: inline-block;}\n.item-head{float:left;width:2em;clear:left;}\n.item-content{margin-left:2em;}\n .foreignobject {line-height:100%; font-size:120%; font-family:STIXgeneral,Times,Symbol,cmr10,CMSY10,CMEX10;padding:0; margin:0; text-align:center; }\nmath {vertical-align:baseline; line-height:100%; font-size:100%; font-family:STIXGeneral,Times,Symbol, cmr10,cmsy10,cmex10,cmmi10; font-style: normal; margin:0; padding:0; }\n\n.entry-title{display: none}\n\ndiv.newtheorem { margin-bottom: 2em; margin-top: 2em; border: 1px solid #333; background: #c7e4da; border-color: #4eb79e;}\ndiv.newtheorem h3 { background: #4eb79e; color: white; padding: 0px 15px 0px 15px; margin-top: 12px}\ndiv.newtheorem p { padding: 15px 15px 15px 15px; }\n\ndiv.newtheorem p span.head .ecbx-1095{font-weight: bold}\ndiv.newtheorem p .ecti-1095{font-style: italic}\ndiv.newtheorem div.custom-itemize{font-style: italic}\ndiv.quote{font-style: italic}\ndiv.newtheorem dl, dl.enumerate {display: grid; grid-template-columns: 5% auto; align-items: start; margin-top: 1em}\ndiv.newtheorem dl dd, dl.enumerate dd {margin-bottom: 0.5em}\ndiv.newtheorem dl dt, dl.enumerate dt {font-weight: normal; margin-top: 0px; text-align: right; margin-right: 15%}\ndiv.newtheorem dl dd {font-style: italic}\ndiv.newtheorem dl dt {font-style: italic}\ndiv.proof p span.ecti-1095 {font-style: italic}\ndiv.figure p img { margin-left: auto; margin-right: auto; display: block; }\ndiv.mefigcentered, div.figure { text-align: center }\n\ndl:after {content:\"\";display:table;clear:both;}\ndd {padding:.5em 0;}\ndl {width:100%;}\ndt, dd {display:inline-block; width:125%;}\ndt {text-align:right; font-weight:bold; clear:left; float:left;}\ndd {width:100%; padding-left:1em; padding-top: 0px; clear:right;}\ndd + dd {float:right; clear:both;}\ndd + dt {clear:both;}\ndt + dt {width: 100%; float: none; padding: 0 70% 0 0;}\ndt + dt + dd {margin-top: -2em;}\ndt + dt + dd + dt {margin-top: 2em;}\n<\/style>\n<style scoped=\"scoped\">\n\/* CSS Analysis-Skript D-Math ETHZ *\/\n\n\/* Uniform Font, also for headers *\/\nh3 {\n\tfont-family: \"Times New Roman\", serif;\n\tmargin-bottom: 35px;\n}\nh4 {\n\tfont-family: \"Times New Roman\", serif;\n}\nh5 {\n\tfont-family: \"Times New Roman\", serif;\n}\n\n\/* Bold font, e.g. for definitions *\/\n.ecbx-1095 {font-weight: 550 ;}\n\n\n\/* Uniform spacing, indent: larger, noindent, enumerate, itemize *\/\np.indent {\n\tmargin: 25px 0px 0px 0px;\n\ttext-indent: 0px; \n}\np.noindent {\n\tmargin: 15px 0px 0px 0px;\n\ttext-indent: 0px; \n}\ndl.enumerate {\n\tmargin: 0px 0px 0px 0px;\n}\ndl.enumerate dt, dl.enumerate dd {\n\tmargin-top: 15px;\n\tmargin-bottom: 0px;\n}\ndiv.custom-itemize {\n\tmargin: 0px 0px 0px 0px;\n}\ndiv.custom-itemize div.item-head {\n\tmargin-top: 15px;\n\tmargin-bottom: 0px;\n\ttext-align: center;\n}\ndiv.custom-itemize div.item-head:first-of-type {\n\tmargin-top: 0px;\n} \ndiv.custom-itemize div.item-content {\n\tmargin-top: 15px;\n\tmargin-bottom: 0px;\n}\n.MJXc-display {\n\tmargin: 15px 0px 0px 0px;\n}\n\n\n\n\/* green metheorem\/melemma CSS class for more\/medium important latex-theorem-environments *\/\n\/* metheorem box+header *\/\ndiv.metheorem {\n    margin-bottom: 40px;\n    margin-top: 40px;\n\tpadding: 0px 15px 15px 15px;\n    border: 1px solid #333;\n    border-color: #4eb79e;\n    background: #c7e4da;\n}\ndiv.metheorem h4 {\n    background: #4eb79e;\n    color: white;\n\tmargin-top: 12px;\n\tmargin-left: -15px;\n\tmargin-right: -15px;\n\tpadding: 0px 15px 0px 15px;\n}\n\/* melemma box+header *\/\ndiv.melemma {\n    margin-bottom: 40px;\n    margin-top: 40px;\n\tpadding: 0px 15px 15px 15px;\n    border: 1px solid #333;\n    border-color: #4eb79e;\n    background: #F2F2F2;\n}\ndiv.melemma h4 {\n    background: #4eb79e;\n    color: white;\n\tmargin-top: 12px;\n\tmargin-left: -15px;\n\tmargin-right: -15px;\n\tpadding: 0px 15px 0px 15px;\n}\n\/* meexample box+header *\/\ndiv.meexample {\n    margin-bottom: 30px;\n    margin-top: 30px;\n\tpadding: 0px 15px 15px 15px;\n\tborder-color: gainsboro;\n\tborder-style: solid;\n\tborder-width: thin;\n}\ndiv.meexample h4 {\n\tfont-size: inherit;\n\tfont-weight: bold;\n    padding: 15px 0px 0px 0px;\n\tmargin-top: 0px;\n\tmargin-bottom: 5px;\n}\ndiv.meexample h4+p.noindent, div.meexample h4+p.indent {\n\tmargin-top: 5px;\n\ttext-indent: 0px;\n}\n\/* padding and margins for stuff inside these boxes, CSS-selector &gt; doesn't work in WP *\/\ndiv.me details {\n\tmargin: 10px 0px 0px 0px;\n}\ndiv.me dd {\n    width: calc(100% - 30px);\n}\t\n\n\n\/* fixing background of pictures *\/\nimg {\n\tbackground: white;\n}\n\n\/* div-container for centered geoapplet *\/\ndiv.geoapplet {\n\tmargin-left: auto;\n\tmargin-right: auto;\n\tmargin-top: 15px;\n\tmax-width: 100%;\n}\ndiv.geoapplet iframe {\n\tborder-style: none;\n\tmax-height: 110vw;\n}\n\n\/* div-container for centered squeezed tables *\/\ndiv.websqueeze {\n\tmargin-left: auto;\n\tmargin-right: auto;\n}\n\n\/* two containers for squeezing text sizes *\/\ndiv.mesmalltext, div.mesmalltext * {\n\tfont-size: 15px;\n}\nspan.metinytext, span.metinytext * {\n\tfont-size: 12px;\n}\n\n\n\/* removing grid lines in equations *\/\n#content table.equation tr td, #content table.equation tr th {\n    border: none;\n}\n#content table.equation {\n    border: none;\n}\n\n\/* hover\/click-solution for short inline explanations and footnotes *\/\n.hover-text {    \/* hidden part *\/\n    display: none;\n}\n.marginpar {     \/* style for footnote as marginpar *\/\n\ttext-decoration: none;\n\tborder: solid;\n\tborder-width: 1pt;\n\tpadding: 3pt;\t\n\twidth: 30%;\n\tbackground: white;\n}\n.hover-trigger { \/* style for hover\/click-trigger text\/symbol *\/\n\tbackground: none;\n\tborder: none;\n\tpadding: 0;\n\toutline: inherit;\t\n\ttext-transform: none;\n\tfont: inherit;\n\tposition: inherit;\n\tvertical-align: baseline;\n    color: #FF7F00;\n\tcursor: help;\n}\n.hover-trigger:hover +.hover-text{\n    display: inline;\n}\n.hover-trigger:active +.hover-text{\n    display: inline;\n}\n\n\/* simplifying style of details\/summary, removing triangle *\/\ndetails summary {\n  background: none;\n  list-style: none;\n  outline: none;\n  cursor: pointer;\n}\ndetails summary::-webkit-details-marker { \n  display: inline;\n  display: none;\n}\n\n\/* MC-True\/False as inline details\/summary *\/\ndetails.mcquest, div.me details.mcquest {\n\tdisplay: inline;\n\tmargin-top: 0px;\n}\nsummary.mcquest {\n\tdisplay: inline;\n\tcolor: #FF7F00;\n\tcursor: help;\n}\n\n\/* proof style: simple black box with gray background \n                little black square at the end on the right *\/\ndiv.proof {\n\tborder-color: black;\n\tborder-style: solid;\n\tborder-width: thin;\n\tbackground-color: #F2F2F2;\n\tpadding: 15px;\n\tmargin-top: 1em; \n}\ndiv.proof p:first-of-type {\n\tmargin: 0px;\n}\ndiv.qed {\n\tmargin-top: -25px;\n\tmargin-bottom: -7px;\n\ttext-align: right;\n}\ntable.equation+div.qed {\n\tmargin-top: -65px;\n}\n\n\/* The following is making also math-formulas inside the headers of Lemmas, etc., white. *\/\ndiv.melemma h4 span {\n    color: white;\n}\ndiv.metheorem h4 span {\n    color: white;\n}\n\n\/* The following are used to avoid fullstop, period, colon, semicolon, and endquote (broader) to move by itself to the next line after a formula.\n   The math-environment before needs to be wrapped in span.maperiod and the fullstop etc. in a span.period --- together they achieve what we want.  *\/\nspan.maperiod {\n       margin-right: 5px;\n}\nspan.period {\n       display: inline-block;\n       width: 0px;\n       margin-left: -5px;\n       margin-right: 4.9px;\n\t   text-indent: 0px;\n}\nspan.maendquote {\n       margin-right: 8px;\n}\nspan.endquote {\n       display: inline-block;\n       width: 0px;\n       margin-left: -8px;\n       margin-right: 7.9px;\n}\n\n\n\/* The following is removing an extra space left of the equation side in aligned equations *\/\nspan.mjx-mtd {\n    padding-left: 0em !important;\n}\n\n\/* The following fixes the weird problem that math appears smaller if it was rendered while the details tag was closed. *\/\ndetails span.mjx-chtml, details span.MathJax_CHTML {\n font-size: 100% !important;\n}\n\n\/* trying to fix line breaks in verbatim, new lines are missing *\/\npre.verbatim {\n\twhite-space: pre-wrap;\n\tfont-size: small;\n}\n<\/style><h3 id=\"z45ab6594496c\" class=\"sectionHead\"><span class=\"titlemark\">6.6 <\/span> <a id=\"x1-1820006\"><\/a>Landau Notation<\/h3> <p class=\"noindent\">Wir f\u00fchren nun zwei gel\u00e4ufige Notationen ein, die das asymptotische Verhalten einer Funktion mit dem asymptotischen Verhalten einer anderen Funktion vergleichen \u2013 also ein relatives asymptotisches Verhalten beschreiben. <\/p><p class=\"indent\">Sei <math display=\"inline\"><mi>D<\/mi> <mo class=\"MathClass-rel\">\u2286<\/mo> <mi>\u211d<\/mi><\/math> eine Teilmenge und <math display=\"inline\"><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <mo class=\"MathClass-rel\">\u2208<\/mo> <mover accent=\"false\" class=\"mml-overline\"><mrow><mi>\u211d<\/mi> <\/mrow><mo accent=\"true\">\u00af<\/mo><\/mover> <\/math> ein H\u00e4ufungspunkt (also mit <math display=\"inline\"><msub><mrow><mover accent=\"true\"><mrow><mi>U<\/mi><\/mrow><mo accent=\"true\">\u02d9<\/mo><\/mover><\/mrow><mrow><mi>\u03b4<\/mi><\/mrow><\/msub> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow> <mo class=\"MathClass-bin\">\u2229<\/mo> <mi>D<\/mi><mo class=\"MathClass-rel\">\u2260<\/mo><mi>\u2205<\/mi><\/math> f\u00fcr alle <math display=\"inline\"><mi>\u03b4<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math>). Seien <math display=\"inline\"><mi>f<\/mi><mo class=\"MathClass-punc\">,<\/mo> <mi>g<\/mi> <mo class=\"MathClass-punc\">:<\/mo> <mi>D<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <mi>\u211d<\/mi><\/math> Funktionen. Wir schreiben <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><mo class=\"MathClass-punc\">,<\/mo><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\">falls ein <math display=\"inline\"><mi>\u03b4<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math> und eine Konstante <math display=\"inline\"><mi>M<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math> existieren, so dass <math display=\"inline\"><mo class=\"MathClass-rel\">|<\/mo><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-rel\">|<\/mo><mo class=\"MathClass-rel\">\u2264<\/mo> <mi>M<\/mi><mo class=\"MathClass-rel\">|<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-rel\">|<\/mo><\/math> f\u00fcr alle <span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>D<\/mi> <mo class=\"MathClass-bin\">\u2229<\/mo><msub><mrow><mover accent=\"true\"><mrow><mi>U<\/mi><\/mrow><mo accent=\"true\">\u02d9<\/mo><\/mover><\/mrow><mrow><mi>\u03b4<\/mi><\/mrow><\/msub> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math><\/span><span class=\"period\">.<\/span> In anderen Worten, <math display=\"inline\"><mi>f<\/mi><\/math> ist \u201e <span class=\"ecbx-1095\">Gross-O<\/span>\u201c  von <math display=\"inline\"><mi>g<\/mi><\/math> f\u00fcr&nbsp;<span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math><\/span><span class=\"period\">,<\/span> falls in einer punktierten Umgebung von&nbsp;<math display=\"inline\"><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math> die Funktion <math display=\"inline\"><mi>f<\/mi><\/math> durch eine Konstante mal <math display=\"inline\"><mo class=\"MathClass-rel\">|<\/mo><mi>g<\/mi><mo class=\"MathClass-rel\">|<\/mo><\/math> beschr\u00e4nkt werden kann. Obwohl dies f\u00fcr obige Defintion nicht notwendig ist, werden wir eigentlich immer vorraussetzen, dass <math display=\"inline\"><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-rel\">\u2260<\/mo><mn>0<\/mn><\/math> f\u00fcr alle <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>D<\/mi><\/math> oder zumindest f\u00fcr alle <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo><msub><mrow><mover accent=\"true\"><mrow><mi>U<\/mi><\/mrow><mo accent=\"true\">\u02d9<\/mo><\/mover><\/mrow><mrow><msub><mrow><mi>\u03b4<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mrow><\/msub> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math> f\u00fcr ein <span class=\"maperiod\"><math display=\"inline\"><msub><mrow><mi>\u03b4<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math><\/span><span class=\"period\">.<\/span> In diesem Fall ist <math display=\"inline\"><mi>f<\/mi><\/math> genau dann Gross-O von <span class=\"maperiod\"><math display=\"inline\"><mi>g<\/mi><\/math><\/span><span class=\"period\">,<\/span>                                                                                                                                                                           wenn <math display=\"inline\"><mfrac><mrow><mi>f<\/mi><\/mrow> <mrow><mi>g<\/mi><\/mrow><\/mfrac><\/math> in einer <math display=\"inline\"><mi>\u03b4<\/mi><\/math>-Umgebung von <math display=\"inline\"><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <\/math> beschr\u00e4nkt ist. Nochmals in anderen Worten ist <math display=\"inline\"><mi>f<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> gleichbedeutend damit, dass <math display=\"inline\"><mi>f<\/mi><\/math> nicht viel gr\u00f6sser als <math display=\"inline\"><mi>g<\/mi><\/math> ist wenn <math display=\"inline\"><mi>x<\/mi><\/math> in der N\u00e4he von <math display=\"inline\"><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math> liegt. Zum Beispiel gilt <\/p> <div class=\"custom-itemize\"><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><math display=\"inline\"><mfrac><mrow><mi>x<\/mi><\/mrow> <mrow><mi>x<\/mi><mo class=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/mfrac> <mo class=\"MathClass-rel\">=<\/mo> <mi>O<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mn>1<\/mn><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math> f\u00fcr <span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><\/math><\/span><span class=\"period\">,<\/span> <\/div><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\">f\u00fcr jedes <math display=\"inline\"><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u211d<\/mi><\/math> gilt <math display=\"inline\"><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <mo class=\"MathClass-rel\">=<\/mo> <mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math><\/span><span class=\"period\">,<\/span> und insbesondere auch <\/div><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><math display=\"inline\"><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <mo class=\"MathClass-rel\">=<\/mo> <mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <mn>0<\/mn><\/math><\/span><span class=\"period\">,<\/span> aber <\/div><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><math display=\"inline\"><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <\/math> ist nicht gleich <math display=\"inline\"><mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><\/math> da <math display=\"inline\"><mfrac><mrow><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <\/mrow> <mrow><mi>x<\/mi><\/mrow><\/mfrac> <mo class=\"MathClass-rel\">=<\/mo> <mi>x<\/mi><\/math> in keiner Umgebung von <math display=\"inline\"><mi>\u221e<\/mi><\/math> beschr\u00e4nkt ist.<\/div><\/div> <p class=\"noindent\">Der Vorteil der Notation ist, dass wir den Namen (oben <math display=\"inline\"><mi>M<\/mi><\/math>) f\u00fcr die obere Schranke nicht einf\u00fchren. Falls uns diese Konstante nicht besonders interessiert, dann k\u00f6nnen wir uns dadurch bei Rechnungen von einer Zeile zur n\u00e4chsten auf das Wesentlich konzentrieren. Man spricht in diesem Zusammenhang auch von der <span class=\"ecbx-1095\">impliziten Konstante<\/span>, falls diese nach einigen Rechenschritten doch erw\u00e4hnt werden muss. <\/p><p class=\"indent\">Wenn <math display=\"inline\"><mi>f<\/mi><\/math> nicht nur durch <math display=\"inline\"><mi>g<\/mi><\/math> beschr\u00e4nkt ist, sondern asymptotisch gegen\u00fcber <math display=\"inline\"><mi>g<\/mi><\/math> vernachl\u00e4ssigbar ist, dann sagen wir, dass <math display=\"inline\"><mi>f<\/mi><\/math> \u201e<span class=\"ecbx-1095\">Klein-o<\/span>\u201c von <math display=\"inline\"><mi>g<\/mi><\/math> ist f\u00fcr&nbsp;<span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math><\/span><span class=\"period\">.<\/span>                                                                                                                                                                           Genauer formuliert: Wir schreiben <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><mo class=\"MathClass-punc\">,<\/mo><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\">falls f\u00fcr jedes <math display=\"inline\"><mi>\ud835\udf00<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math> ein <math display=\"inline\"><mi>\u03b4<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math> existiert mit <math display=\"inline\"><mo class=\"MathClass-rel\">|<\/mo><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-rel\">|<\/mo> <mo class=\"MathClass-rel\">\u2264<\/mo> <mi>\ud835\udf00<\/mi><mo class=\"MathClass-rel\">|<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-rel\">|<\/mo><\/math> f\u00fcr alle <span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>D<\/mi> <mo class=\"MathClass-bin\">\u2229<\/mo><msub><mrow> <mover accent=\"true\"><mrow><mi>U<\/mi><\/mrow><mo accent=\"true\">\u02d9<\/mo><\/mover> <\/mrow><mrow><mi>\u03b4<\/mi><\/mrow><\/msub> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math><\/span><span class=\"period\">.<\/span> Wie zuvor wollen wir meist&nbsp;<math display=\"inline\"><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-rel\">\u2260<\/mo><mn>0<\/mn><\/math> auf&nbsp;<math display=\"inline\"><mi>D<\/mi><\/math> annehmen. In diesem Fall gilt <math display=\"inline\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <\/math> genau dann, wenn <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><munder class=\"msub\"><mrow><mi class=\"qopname\"> lim<\/mi><mo>  <\/mo><\/mrow><mrow><mi>x<\/mi><mo class=\"MathClass-rel\">\u2192<\/mo><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mrow><\/munder><mfrac><mrow><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/mrow> <mrow><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/mrow><\/mfrac> <mo class=\"MathClass-rel\">=<\/mo> <mn>0<\/mn><mo class=\"MathClass-punc\">.<\/mo><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\">Man beachte, dass, falls die eigentlichen Grenzwerte <math display=\"inline\"><munder class=\"msub\"><mrow><mi class=\"qopname\">lim<\/mi><mo>  <\/mo><\/mrow><mrow><mi>x<\/mi><mo class=\"MathClass-rel\">\u2192<\/mo><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub><\/mrow><\/munder><mi>f<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math> und <math display=\"inline\"><munder class=\"msub\"><mrow><mi class=\"qopname\">lim<\/mi><mo>  <\/mo><\/mrow><mrow><mi>x<\/mi><mo class=\"MathClass-rel\">\u2192<\/mo><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub><\/mrow><\/munder><mi>g<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi> <\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math> existieren und nicht Null sind, sicherlich <math display=\"inline\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <\/math> erf\u00fcllt ist, aber die st\u00e4rkere Aussage <math display=\"inline\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <\/math>                                                                                                                                                                           falsch ist. Beide Notationen sind also vor allem dann interessant, wenn die Grenzwerte entweder null oder unendlich sind. Zum Beispiel gilt <\/p> <div class=\"custom-itemize\"><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><\/math> (aber nicht umgekehrt) und <\/div><div class=\"item-head\"> <span class=\"tcrm-1095\">\u2022<\/span><\/div><div class=\"item-content\"><math display=\"inline\"><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msup> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <mn>0<\/mn><\/math> (aber nicht umgekehrt).<\/div><\/div> <p class=\"indent\">Diese Notationen machen analog Sinn f\u00fcr andere Bewegungen wie zum Beispiel&nbsp;<span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2198<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math><\/span><span class=\"period\">,<\/span> allgemeine Filter, und k\u00f6nnen insbesondere auch f\u00fcr Folgen verwendet werden. <\/p> <div class=\"me meexample\"> <div class=\"wp-nocaption \"><\/div><h4 id=\"z3a0314f82193\"> <a id=\"x1-182001r52\"><\/a> <span class=\"ecbx-1095\">\u00dc<\/span><span class=\"ecbx-1095\">bung 6.52 <\/span>(Klein-o Asymptotiken)<span class=\"ecbx-1095\">.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Zeigen Sie, dass die Asymptotiken<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\" \/> <mtd class=\"align-even\"><msup><mrow><mi>x<\/mi><\/mrow><mrow><mi>p<\/mi><\/mrow><\/msup> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <mn>0<\/mn><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"qquad\" width=\"2em\" \/><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-odd\" columnalign=\"right\"><mi>x<\/mi> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><msup><mrow><mi>x<\/mi><\/mrow><mrow><mi>p<\/mi><\/mrow><\/msup><mo class=\"MathClass-close\">)<\/mo><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><mtr><mtd class=\"align-odd\" columnalign=\"right\" \/> <mtd class=\"align-even\"><msup><mrow><mi>x<\/mi><\/mrow><mrow><mi>a<\/mi><\/mrow><\/msup> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><msup><mrow><mi>e<\/mi><\/mrow><mrow><mi>x<\/mi><\/mrow><\/msup><mo class=\"MathClass-close\">)<\/mo><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"qquad\" width=\"2em\" \/><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-odd\" columnalign=\"right\"><mi class=\"qopname\">log<\/mi><mo>  <\/mo><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><msup><mrow><mi>x<\/mi><\/mrow><mrow><mi>b<\/mi><\/mrow><\/msup><mo class=\"MathClass-close\">)<\/mo><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\"><span class=\"ecti-1095\">f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r jedes <\/span><span class=\"maperiod\"><math display=\"inline\"><mi>p<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>1<\/mn><\/math><\/span><span class=\"period\">,<\/span> <math display=\"inline\"><mi>a<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u211d<\/mi><\/math> <span class=\"ecti-1095\">und<\/span> <math display=\"inline\"><mi>b<\/mi> <mo class=\"MathClass-rel\">&gt;<\/mo> <mn>0<\/mn><\/math> <span class=\"ecti-1095\">zutreffen, wobei sie <\/span><span class=\"ecti-1095\">\u00dc<\/span><span class=\"ecti-1095\">bung <\/span><a href=\"..\/..\/chapter\/die-exponentialfunktion#x1-173005r35\"><span class=\"ecti-1095\">6.35<\/span><\/a> <span class=\"ecti-1095\">verwenden d<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">rfen.<\/span> <\/p> <\/div> <div class=\"me meexample\"> <div class=\"wp-nocaption \"><\/div><h4 id=\"zcdf36be99637\"> <a id=\"x1-182002r53\"><\/a> <span class=\"ecbx-1095\">\u00dc<\/span><span class=\"ecbx-1095\">bung 6.53 <\/span>(Rechnen mit der Landau Notation)<span class=\"ecbx-1095\">.<\/span> <\/h4> <p class=\"indent\"><span class=\"ecti-1095\">Seien <\/span><math display=\"inline\"><mi>D<\/mi><mo class=\"MathClass-punc\">,<\/mo><msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/math> <span class=\"ecti-1095\">wie oben<\/span> <span class=\"ecti-1095\">und <\/span><math display=\"inline\"><mi>f<\/mi><mo class=\"MathClass-punc\">,<\/mo> <msub><mrow><mi>f<\/mi><\/mrow><mrow><mn>1<\/mn> <\/mrow> <\/msub> <mo class=\"MathClass-punc\">,<\/mo> <msub><mrow><mi>f<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msub><mo class=\"MathClass-punc\">,<\/mo><mi>g<\/mi><\/math> <span class=\"ecti-1095\">reellwertige<\/span> <span class=\"ecti-1095\">Funktionen auf <\/span><span class=\"maperiod\"><math display=\"inline\"><mi>D<\/mi><\/math><\/span><span class=\"period\">.<\/span> <span class=\"ecti-1095\">Zeigen Sie, dass falls <\/span><math display=\"inline\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-punc\">,<\/mo><mspace class=\"nbsp\" width=\"0.33em\" \/><msub><mrow><mi>f<\/mi><\/mrow><mrow><mn>1<\/mn><\/mrow><\/msub><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">und <\/span><math display=\"inline\"><mspace class=\"nbsp\" width=\"0.33em\" \/><msub><mrow><mi>f<\/mi><\/mrow><mrow><mn>2<\/mn> <\/mrow> <\/msub> <mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><\/math> <span class=\"ecti-1095\">f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r <\/span><span class=\"maperiod\"><math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <\/math><\/span><span class=\"period\">,<\/span> <span class=\"ecti-1095\">dann auch<\/span> <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><msub><mrow><mi>f<\/mi><\/mrow><mrow><mn>1<\/mn><\/mrow><\/msub><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-bin\">+<\/mo> <msub><mrow><mi>f<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msub><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/mtd> <mtd class=\"align-even\"> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><mo class=\"MathClass-punc\">,<\/mo><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"> <mspace width=\"2em\" \/><\/mtd><\/mtr><mtr><mtd class=\"align-odd\" columnalign=\"right\"><mi>\u03b1<\/mi><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/mtd> <mtd class=\"align-even\"> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"> <mspace width=\"2em\" \/><\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\"><span class=\"ecti-1095\">f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r <\/span><math display=\"inline\"><mi>\u03b1<\/mi> <mo class=\"MathClass-rel\">\u2208<\/mo> <mi>\u211d<\/mi><\/math> <span class=\"ecti-1095\">und analog f<\/span><span class=\"ecti-1095\">\u00fc<\/span><span class=\"ecti-1095\">r Gross-O.<\/span> <\/p> <\/div> <p class=\"indent\">Die Landau Notation wird in vielen Situationen auch als Platzhalter verwendet, um beispielsweise auszudr\u00fccken, dass ein Term in einer Summe schneller anw\u00e4chst oder abf\u00e4llt als die anderen. In einem Ausdruck der Form                                                                                                                                                                           <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mi>f<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-bin\">+<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\">steht der Term <math display=\"inline\"><mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><\/math> f\u00fcr eine implizite Funktion <math display=\"inline\"><mi>h<\/mi> <mo class=\"MathClass-punc\">:<\/mo> <mi>D<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <mi>\u211d<\/mi><\/math> mit der Eigenschaft <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mi>h<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>g<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn><\/mrow><\/msub><mo class=\"MathClass-punc\">,<\/mo><\/mtd> <mtd class=\"align-even\"><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\"> <\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\">also soll <math display=\"inline\"><mover accent=\"true\"><mrow><mi>f<\/mi><\/mrow><mo accent=\"true\">~<\/mo><\/mover> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow> <mo class=\"MathClass-rel\">=<\/mo> <mi>f<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow> <mo class=\"MathClass-bin\">+<\/mo> <mi>o<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>g<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math> die Asymptotik <math display=\"inline\"><mover accent=\"true\"><mrow><mi>f<\/mi><\/mrow><mo accent=\"true\">~<\/mo><\/mover> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow> <mo class=\"MathClass-bin\">\u2212<\/mo> <mi>f<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow> <mo class=\"MathClass-rel\">=<\/mo> <mi>h<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow> <mo class=\"MathClass-rel\">=<\/mo> <mi>o<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>g<\/mi> <mrow><mo fence=\"true\" form=\"prefix\"> (<\/mo><mrow><mi>x<\/mi><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/math> f\u00fcr <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <msub><mrow><mi>x<\/mi><\/mrow><mrow><mn>0<\/mn> <\/mrow> <\/msub> <\/math> erf\u00fcllen. Dies gilt analog ebenso f\u00fcr die Gross-O Notation. <\/p><p class=\"indent\">Beispielsweise schreibt man (nach Polynomdivision mit Rest) <\/p><math display=\"block\"><mtable class=\"align-star\" columnalign=\"left\"> <mtr><mtd class=\"align-odd\" columnalign=\"right\"><mfrac><mrow><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>3<\/mn><\/mrow><\/msup> <mo class=\"MathClass-bin\">\u2212<\/mo> <mn>7<\/mn><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msup> <mo class=\"MathClass-bin\">+<\/mo> <mn>6<\/mn><mi>x<\/mi> <mo class=\"MathClass-bin\">+<\/mo> <mn>2<\/mn><\/mrow> <mrow><msup><mrow><mi>x<\/mi><\/mrow><mrow><mn>2<\/mn><\/mrow><\/msup> <mo class=\"MathClass-bin\">+<\/mo> <mi>x<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mn>3<\/mn><mn>4<\/mn><\/mrow><\/mfrac> <\/mtd> <mtd class=\"align-even\"> <mo class=\"MathClass-rel\">=<\/mo> <mi>x<\/mi> <mo class=\"MathClass-bin\">\u2212<\/mo> <mn>8<\/mn> <mo class=\"MathClass-bin\">+<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"> <mspace width=\"2em\" \/><\/mtd><\/mtr><mtr><mtd class=\"align-odd\" columnalign=\"right\" \/> <mtd class=\"align-even\"> <mo class=\"MathClass-rel\">=<\/mo> <mi>x<\/mi> <mo class=\"MathClass-bin\">+<\/mo> <mi>O<\/mi><mo class=\"MathClass-open\">(<\/mo><mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"> <mspace width=\"2em\" \/><\/mtd><\/mtr><mtr><mtd class=\"align-odd\" columnalign=\"right\" \/> <mtd class=\"align-even\"> <mo class=\"MathClass-rel\">=<\/mo> <mi>x<\/mi> <mo class=\"MathClass-bin\">+<\/mo> <mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><mspace class=\"quad\" width=\"1em\" \/><mstyle class=\"text\"><mtext>&nbsp;f\u00fcr&nbsp;<\/mtext><\/mstyle><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo><mi>\u221e<\/mi><mo class=\"MathClass-punc\">,<\/mo><mspace width=\"2em\" \/><\/mtd> <mtd class=\"align-label\" columnalign=\"right\" \/> <mtd class=\"align-label\"> <mspace width=\"2em\" \/><\/mtd><\/mtr><\/mtable><\/math> <p class=\"noindent\">und erinnert sich auf der rechten Seite somit nur an jene Terme, die den Hauptteil der Bewegung <math display=\"inline\"><mi>x<\/mi> <mo class=\"MathClass-rel\">\u2192<\/mo> <mi>\u221e<\/mi><\/math> ausmacht. Es mag vielleicht \u00fcberraschen, dass im obigen Beispiel alle drei Formeln zutreffen oder n\u00fctzlich sein k\u00f6nnten. Doch folgen diese Behauptungen direkt aus der Polynomdivision und je nach Zusammenhang will man vielleicht die etwas genauere Aussage mit Fehler <math display=\"inline\"><mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mn>1<\/mn><mo class=\"MathClass-close\">)<\/mo><\/math> oder die gr\u00f6bere Aussage mit Hilfe des Fehlers <math display=\"inline\"><mi>o<\/mi><mo class=\"MathClass-open\">(<\/mo><mi>x<\/mi><mo class=\"MathClass-close\">)<\/mo><\/math> verwenden. <\/p><p class=\"indent\">Derartige asymptotische Aussagen helfen in komplizierteren Argumenten und Berechnungen den Fokus auf die wesentlichen Teile einer Berechnungen zu lenken. Doch liegen in diesem Verstecken von gewissen Ausdr\u00fccken auch Risiken f\u00fcr Fehler, zum Beispiel wenn wir die Fehlerterme unbeschr\u00e4nkt oft addieren wollen oder die Fehlerterme von weiteren Parametern abh\u00e4ngen und diese Abh\u00e4ngigkeit auf Grund der Notation vergessen wird. Wir werden die Landau Notation sporadisch aber doch immer wieder einmal einsetzen um das Wesentliche an einer Aussage zu betonen.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               <a id=\"x1-182003r182\"><\/a> <\/p> \n","protected":false},"author":1089,"menu_order":6,"template":"","meta":{"pb_show_title":"","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-73","chapter","type-chapter","status-publish","hentry"],"part":67,"_links":{"self":[{"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/pressbooks\/v2\/chapters\/73","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/wp\/v2\/users\/1089"}],"version-history":[{"count":0,"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/pressbooks\/v2\/chapters\/73\/revisions"}],"part":[{"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/pressbooks\/v2\/parts\/67"}],"metadata":[{"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/pressbooks\/v2\/chapters\/73\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/wp\/v2\/media?parent=73"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/pressbooks\/v2\/chapter-type?post=73"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/wp\/v2\/contributor?post=73"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/wp-prd.let.ethz.ch\/analysis19\/wp-json\/wp\/v2\/license?post=73"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}