"use strict"; const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0]; const {useMDXComponents: _provideComponents} = arguments[0]; function _createMdxContent(props) { const _components = { a: "a", annotation: "annotation", div: "div", h1: "h1", hr: "hr", img: "img", li: "li", math: "math", mfrac: "mfrac", mi: "mi", mn: "mn", mo: "mo", mrow: "mrow", mspace: "mspace", msub: "msub", msup: "msup", mtext: "mtext", p: "p", path: "path", semantics: "semantics", span: "span", strong: "strong", svg: "svg", table: "table", tbody: "tbody", td: "td", th: "th", thead: "thead", tr: "tr", ul: "ul", ..._provideComponents(), ...props.components }; return _jsxs(_Fragment, { children: [_jsx(_components.p, { children: "#eth #exercise" }), "\n", _jsxs(_components.h1, { id: "41-applying-the-master-theorem", children: [_jsx(_components.a, { className: "heading-link", href: "#41-applying-the-master-theorem", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "4.1 Applying the ", _jsx(_components.a, { href: "/Programming/Algorithms+%26+Data+Structures+ETH/Master+Theorem", className: "internal", "data-fs-resolved-file-path": "/Programming/Algorithms & Data Structures ETH/Master Theorem.md", children: "master theorem" })] }), "\n", _jsxs(_components.p, { children: ["a)\n", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "a" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "4" }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mi, { children: "b" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "a=4, b=1" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.8889em", verticalAlign: "-0.1944em" } }), _jsx(_components.span, { className: "mord", children: "4" }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "b" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] })] }), "\n", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { children: "<" }), _jsxs(_components.msub, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "log" }), _jsx(_components.mo, { children: "⁡" })] }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mn, { children: "4" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "1<\\log_{2}4=2" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6835em", verticalAlign: "-0.0391em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "<" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.9386em", verticalAlign: "-0.2441em" } }), _jsxs(_components.span, { className: "mop", children: [_jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.01389em" }, children: "g" })] }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.207em" }, children: _jsxs(_components.span, { style: { top: "-2.4559em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.2441em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord", children: "4" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "2" })] })] })] }), "\nAccording to the third case of the master theorem ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "T" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "≤" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsxs(_components.mrow, { children: [_jsxs(_components.msub, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "log" }), _jsx(_components.mo, { children: "⁡" })] }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mn, { children: "4" })] })] }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "≤" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T(n)\\leq O(n^{\\log_{2}4})\\leq O(n^{2})" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.13889em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "≤" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0991em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.02778em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8491em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsxs(_components.span, { className: "mord mtight", children: [_jsxs(_components.span, { className: "mop mtight", children: [_jsxs(_components.span, { className: "mop mtight", children: [_jsx(_components.span, { className: "mtight", children: "l" }), _jsx(_components.span, { className: "mtight", children: "o" }), _jsx(_components.span, { className: "mtight", style: { marginRight: "0.01389em" }, children: "g" })] }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.1944em" }, children: _jsxs(_components.span, { style: { top: "-2.2341em", marginRight: "0.0714em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.5em" } }), _jsx(_components.span, { className: "sizing reset-size3 size1 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.2659em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mspace mtight", style: { marginRight: "0.1952em" } }), _jsx(_components.span, { className: "mord mtight", children: "4" })] }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "≤" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0641em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.02778em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8141em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] })] }), "\n", _jsxs(_components.p, { children: ["b)\n", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "a" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mi, { children: "b" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "a=1, b=1" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.8889em", verticalAlign: "-0.1944em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "b" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] })] }), "\n", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { children: ">" }), _jsxs(_components.msub, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "log" }), _jsx(_components.mo, { children: "⁡" })] }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "0" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "1>\\log_{2}1=0" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6835em", verticalAlign: "-0.0391em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: ">" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.9386em", verticalAlign: "-0.2441em" } }), _jsxs(_components.span, { className: "mop", children: [_jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.01389em" }, children: "g" })] }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.207em" }, children: _jsxs(_components.span, { style: { top: "-2.4559em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.2441em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "0" })] })] })] }), "\nAccording to the first case of the master theorem ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "T" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "≤" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T(n)\\leq O(n)" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.13889em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "≤" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.02778em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] })] }), "\n", _jsxs(_components.p, { children: ["c)\n", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "a" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "4" }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mi, { children: "b" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "a=4, b=2" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.8889em", verticalAlign: "-0.1944em" } }), _jsx(_components.span, { className: "mord", children: "4" }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "b" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "2" })] })] })] }), "\n", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mn, { children: "2" }), _jsx(_components.mo, { children: "=" }), _jsxs(_components.msub, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "log" }), _jsx(_components.mo, { children: "⁡" })] }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mn, { children: "4" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "2= \\log_{2}4=2" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.9386em", verticalAlign: "-0.2441em" } }), _jsxs(_components.span, { className: "mop", children: [_jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.01389em" }, children: "g" })] }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.207em" }, children: _jsxs(_components.span, { style: { top: "-2.4559em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.2441em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord", children: "4" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "2" })] })] })] }), "\nAccording to the second case of the master theorem ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "T" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "≤" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsxs(_components.mrow, { children: [_jsxs(_components.msub, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "log" }), _jsx(_components.mo, { children: "⁡" })] }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mn, { children: "4" })] })] }), _jsx(_components.mi, { children: "log" }), _jsx(_components.mo, { children: "⁡" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "≤" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mi, { children: "log" }), _jsx(_components.mo, { children: "⁡" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T(n)\\leq O(n^{\\log_{2}4}\\log n)\\leq O(n^{2}\\log n)" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.13889em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "≤" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0991em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.02778em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8491em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsxs(_components.span, { className: "mord mtight", children: [_jsxs(_components.span, { className: "mop mtight", children: [_jsxs(_components.span, { className: "mop mtight", children: [_jsx(_components.span, { className: "mtight", children: "l" }), _jsx(_components.span, { className: "mtight", children: "o" }), _jsx(_components.span, { className: "mtight", style: { marginRight: "0.01389em" }, children: "g" })] }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.1944em" }, children: _jsxs(_components.span, { style: { top: "-2.2341em", marginRight: "0.0714em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.5em" } }), _jsx(_components.span, { className: "sizing reset-size3 size1 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.2659em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mspace mtight", style: { marginRight: "0.1952em" } }), _jsx(_components.span, { className: "mord mtight", children: "4" })] }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.01389em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "≤" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0641em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.02778em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8141em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.01389em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] })] }), "\n", _jsxs(_components.h1, { id: "42-asymptotic-notations", children: [_jsx(_components.a, { className: "heading-link", href: "#42-asymptotic-notations", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "4.2 Asymptotic notations"] }), "\n", _jsxs(_components.p, { children: ["a)\n", _jsx(_components.img, { src: "https://obvault-thecyberweaver.flowershow.me/assets/Pasted%20image%2020251016222246.png", alt: "Pasted image 20251016222246", className: "internal", "data-fs-resolved-file-path": "/assets/Pasted image 20251016222246.png" }), "\nb)\n", _jsx(_components.img, { src: "https://obvault-thecyberweaver.flowershow.me/assets/Pasted%20image%2020251016222315.png", alt: "Pasted image 20251016222315", className: "internal", "data-fs-width": "508", "data-fs-resolved-file-path": "/assets/Pasted image 20251016222315.png" })] }), "\n", _jsxs(_components.h1, { id: "43-one-looped-sort", children: [_jsx(_components.a, { className: "heading-link", href: "#43-one-looped-sort", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "4.3 One-Looped Sort"] }), "\n", _jsx(_components.p, { children: "a)" }), "\n", _jsx(_components.div, { className: "overflow-x-auto", children: _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { style: { textAlign: "right" }, children: "Iteration" }), _jsx(_components.th, { style: { textAlign: "right" }, children: "i after iteration" }), _jsx(_components.th, { children: "A" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "right" }, children: "1" }), _jsx(_components.td, { style: { textAlign: "right" }, children: "1" }), _jsx(_components.td, { children: "[10, 20, 30, 40, 50, 25]" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "right" }, children: "2" }), _jsx(_components.td, { style: { textAlign: "right" }, children: "2" }), _jsx(_components.td, { children: "[10, 20, 30, 40, 50, 25]" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "right" }, children: "3" }), _jsx(_components.td, { style: { textAlign: "right" }, children: "3" }), _jsx(_components.td, { children: "[10, 20, 30, 40, 50, 25]" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "right" }, children: "4" }), _jsx(_components.td, { style: { textAlign: "right" }, children: "4" }), _jsx(_components.td, { children: "[10, 20, 30, 40, 50, 25]" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "right" }, children: "5" }), _jsx(_components.td, { style: { textAlign: "right" }, children: "5" }), _jsx(_components.td, { children: "[10, 20, 30, 40, 50, 25]" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "right" }, children: "6" }), _jsx(_components.td, { style: { textAlign: "right" }, children: "4" }), _jsx(_components.td, { children: "[10, 20, 30, 40, 25, 50]" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "right" }, children: "7" }), _jsx(_components.td, { style: { textAlign: "right" }, children: "3" }), _jsx(_components.td, { children: "[10, 20, 30, 25, 40, 50]" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "right" }, children: "8" }), _jsx(_components.td, { style: { textAlign: "right" }, children: "2" }), _jsx(_components.td, { children: "[10, 20, 25, 30, 40, 50]" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "right" }, children: "9" }), _jsx(_components.td, { style: { textAlign: "right" }, children: "3" }), _jsx(_components.td, { children: "[10, 20, 25, 30, 40, 50]" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "right" }, children: "10" }), _jsx(_components.td, { style: { textAlign: "right" }, children: "4" }), _jsx(_components.td, { children: "[10, 20, 25, 30, 40, 50]" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "right" }, children: "11" }), _jsx(_components.td, { style: { textAlign: "right" }, children: "5" }), _jsx(_components.td, { children: "[10, 20, 25, 30, 40, 50]" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "right" }, children: "12" }), _jsx(_components.td, { style: { textAlign: "right" }, children: "6" }), _jsx(_components.td, { children: "[10, 20, 25, 30, 40, 50]" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "right" }, children: "b)" }), _jsx(_components.td, { style: { textAlign: "right" } }), _jsx(_components.td, {})] }), _jsxs(_components.tr, { children: [_jsxs(_components.td, { style: { textAlign: "right" }, children: [_jsx(_components.strong, { children: "Invariant" }), ": At the moment when the variable ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "i" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "i" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) })] }), " gets incremented to a new value ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "i" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mi, { children: "k" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "i = k" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6944em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" })] })] })] }), " for the first time, the first k elements of the array are sorted in increasing order."] }), _jsx(_components.td, { style: { textAlign: "right" } }), _jsx(_components.td, {})] }), _jsxs(_components.tr, { children: [_jsxs(_components.td, { style: { textAlign: "right" }, children: [_jsx(_components.strong, { children: "Base" }), ": ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "k=1" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6944em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] })] }), ", The first one element (or ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "A" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mn, { children: "0" }), _jsx(_components.mo, { stretchy: "false", children: "]" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "A[0]" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "A" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord", children: "0" }), _jsx(_components.span, { className: "mclose", children: "]" })] }) })] }), ") is always sorted"] }), _jsx(_components.td, { style: { textAlign: "right" } }), _jsx(_components.td, {})] }), _jsxs(_components.tr, { children: [_jsxs(_components.td, { style: { textAlign: "right" }, children: [_jsx(_components.strong, { children: "IS" }), ": ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { children: "→" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "k\\to k+1" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6944em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "→" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7778em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] })] })] }), _jsx(_components.td, { style: { textAlign: "right" } }), _jsx(_components.td, {})] })] })] }) }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["If ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "A" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { stretchy: "false", children: "]" }), _jsx(_components.mo, { children: "≥" }), _jsx(_components.mi, { children: "A" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: "]" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "A[k]\\geq A[k-1]" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "A" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mclose", children: "]" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "≥" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "A" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: "]" })] })] })] }), ", then the first ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "k" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "k" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6944em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" })] }) })] }), " elements ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "A" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mn, { children: "0" }), _jsx(_components.mo, { children: "…" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: "]" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "A[0\\dots k-1]" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "A" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord", children: "0" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "minner", children: "…" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: "]" })] })] })] }), " are already sorted. Then ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "i" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "i" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) })] }), " is incremented to ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "k+1" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7778em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] })] }), ", so that the next new position will be inspected."] }), "\n", _jsxs(_components.li, { children: ["If ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "A" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { stretchy: "false", children: "]" }), _jsx(_components.mo, { children: "<" }), _jsx(_components.mi, { children: "A" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: "]" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "A[k]< A[k-1]" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "A" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mclose", children: "]" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "<" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "A" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: "]" })] })] })] }), ", then the algorithm swaps ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "A" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { stretchy: "false", children: "]" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "A[k]" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "A" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mclose", children: "]" })] }) })] }), " and ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "A" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: "]" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "A[k+1]" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "A" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: "]" })] })] })] }), " and ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "i" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "i" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) })] }), " is set to ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "i" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "i-1" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7429em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] })] }), ". This step repeatedly moves the current unsorted element to the left, until it gets to the right position. After the element gets to the right position, the first ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "k" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "k" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6944em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" })] }) })] }), " elements ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "A" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mn, { children: "0" }), _jsx(_components.mo, { children: "…" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: "]" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "A[0\\dots k-1]" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "A" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord", children: "0" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "minner", children: "…" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: "]" })] })] })] }), " are sorted. ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "i" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "i" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) })] }), " will then be continuously incremented until it meets a new value ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "i" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "i=k+1" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7778em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] })] }), ", so that the next new position will be inspected.\nBy induction, every time ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "i" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "i" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) })] }), " is increased to k, ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "A" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mn, { children: "0" }), _jsx(_components.mo, { children: "…" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: "]" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "A[0\\dots k-1]" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "A" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord", children: "0" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "minner", children: "…" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.03148em" }, children: "k" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: "]" })] })] })] }), " is sorted."] }), "\n"] }), "\n", _jsxs(_components.p, { children: ["c)\n", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(n^{2})" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0641em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.02778em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8141em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] })] }), "\n", _jsxs(_components.h1, { id: "44-searching-for-the-summit", children: [_jsx(_components.a, { className: "heading-link", href: "#44-searching-for-the-summit", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "4.4 Searching for the summit"] }), "\n", _jsx(_components.p, { children: "a)" }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.p, { children: [_jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "B" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mn, { children: "0" }), _jsx(_components.mo, { stretchy: "false", children: "]" }), _jsx(_components.mo, { children: "←" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mi, { mathvariant: "normal", children: "∞" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "B[0]\\leftarrow-\\infty" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.05017em" }, children: "B" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord", children: "0" }), _jsx(_components.span, { className: "mclose", children: "]" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "←" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6667em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "−" }), _jsx(_components.span, { className: "mord", children: "∞" })] })] })] }), "\n", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "B" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { children: "…" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: "]" }), _jsx(_components.mo, { children: "←" }), _jsx(_components.mi, { children: "A" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { children: "…" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: "]" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "B[1\\dots n]\\leftarrow A[1\\dots n]" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.05017em" }, children: "B" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "minner", children: "…" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: "]" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "←" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "A" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "minner", children: "…" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: "]" })] })] })] }), "\n", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "B" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: "]" }), _jsx(_components.mo, { children: "←" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mi, { mathvariant: "normal", children: "∞" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "B[n+1]\\leftarrow -\\infty" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.05017em" }, children: "B" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: "]" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "←" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6667em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "−" }), _jsx(_components.span, { className: "mord", children: "∞" })] })] })] }), "\nwhile ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "l" }), _jsx(_components.mo, { children: "≤" }), _jsx(_components.mi, { children: "r" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "l\\leq r" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.8304em", verticalAlign: "-0.136em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.01968em" }, children: "l" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "≤" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.02778em" }, children: "r" })] })] })] }), " do:\n", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mspace, { width: "1em" }), _jsx(_components.mi, { children: "m" }), _jsx(_components.mo, { children: "←" }), _jsxs(_components.mrow, { children: [_jsx(_components.mo, { fence: "true", children: "⌊" }), _jsxs(_components.mfrac, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "l" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mi, { children: "r" })] }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mo, { fence: "true", children: "⌋" })] })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "\\quad m\\leftarrow \\left\\lfloor \\frac{l+r}{2} \\right\\rfloor" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mspace", style: { marginRight: "1em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "m" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "←" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.2301em", verticalAlign: "-0.35em" } }), _jsxs(_components.span, { className: "minner", children: [_jsx(_components.span, { className: "mopen delimcenter", style: { top: "0em" }, children: _jsx(_components.span, { className: "delimsizing size1", children: "⌊" }) }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mopen nulldelimiter" }), _jsx(_components.span, { className: "mfrac", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsxs(_components.span, { className: "vlist", style: { height: "0.8801em" }, children: [_jsxs(_components.span, { style: { top: "-2.655em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }), _jsxs(_components.span, { style: { top: "-3.23em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3em" } }), _jsx(_components.span, { className: "frac-line", style: { borderBottomWidth: "0.04em" } })] }), _jsxs(_components.span, { style: { top: "-3.394em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsxs(_components.span, { className: "mord mtight", children: [_jsx(_components.span, { className: "mord mathnormal mtight", style: { marginRight: "0.01968em" }, children: "l" }), _jsx(_components.span, { className: "mbin mtight", children: "+" }), _jsx(_components.span, { className: "mord mathnormal mtight", style: { marginRight: "0.02778em" }, children: "r" })] }) })] })] }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.345em" }, children: _jsx(_components.span, {}) }) })] }) }), _jsx(_components.span, { className: "mclose nulldelimiter" })] }), _jsx(_components.span, { className: "mclose delimcenter", style: { top: "0em" }, children: _jsx(_components.span, { className: "delimsizing size1", children: "⌋" }) })] })] })] })] }), "\n", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mspace, { width: "1em" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "\\quad" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0em" } }), _jsx(_components.span, { className: "mspace", style: { marginRight: "1em" } })] }) })] }), "if ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "B" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "m" }), _jsx(_components.mo, { stretchy: "false", children: "]" }), _jsx(_components.mo, { children: ">" }), _jsx(_components.mi, { children: "B" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "m" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: "]" }), _jsx(_components.mtext, { children: " and " }), _jsx(_components.mi, { children: "B" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "m" }), _jsx(_components.mo, { stretchy: "false", children: "]" }), _jsx(_components.mo, { children: ">" }), _jsx(_components.mi, { children: "B" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "m" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: "]" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "B[m]>B[m+1] \\text{ and } B[m]>B[m-1]" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.05017em" }, children: "B" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord mathnormal", children: "m" }), _jsx(_components.span, { className: "mclose", children: "]" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: ">" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.05017em" }, children: "B" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord mathnormal", children: "m" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: "]" }), _jsx(_components.span, { className: "mord text", children: _jsx(_components.span, { className: "mord", children: " and " }) }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.05017em" }, children: "B" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord mathnormal", children: "m" }), _jsx(_components.span, { className: "mclose", children: "]" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: ">" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.05017em" }, children: "B" }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord mathnormal", children: "m" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: "]" })] })] })] }), " then\n", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mspace, { width: "2em" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "\\qquad" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0em" } }), _jsx(_components.span, { className: "mspace", style: { marginRight: "2em" } })] }) })] }), "return ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "m" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "m" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "m" })] }) })] }), "\n", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mspace, { width: "1em" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "\\quad" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0em" } }), _jsx(_components.span, { className: "mspace", style: { marginRight: "1em" } })] }) })] }), "else if ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "B" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "m" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: "]" }), _jsx(_components.mo, { children: "<" }), _jsx(_components.mi, { children: "B" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "m" }), _jsx(_components.mo, { stretchy: "false", children: "]" }), _jsx(_components.mo, { children: "<" }), _jsx(_components.mi, { children: "B" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mi, { children: "m" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: "]" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "B[m-1]