"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", h2: "h2", li: "li", math: "math", mi: "mi", mn: "mn", mo: "mo", mrow: "mrow", msub: "msub", msup: "msup", p: "p", path: "path", semantics: "semantics", span: "span", strong: "strong", svg: "svg", ul: "ul", ..._provideComponents(), ...props.components }; return _jsxs(_Fragment, { children: [_jsxs(_components.h1, { id: "karatsuba-multiplication", children: [_jsx(_components.a, { className: "heading-link", href: "#karatsuba-multiplication", 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" }) }) }), "Karatsuba multiplication"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.a, { href: "https://obvault-thecyberweaver.flowershow.me/Karatsuba%20Multiplikation.excalidraw", className: "internal new unsupported", target: "_blank", rel: "noopener noreferrer", children: "Karatsuba Multiplikation.excalidraw" }), "\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: [_jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "10" }), _jsx(_components.mi, { children: "n" })] }), _jsx(_components.mi, { children: "a" }), _jsx(_components.mi, { children: "c" }), _jsx(_components.mo, { children: "+" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "10" }), _jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mi, { mathvariant: "normal", children: "/" }), _jsx(_components.mn, { children: "2" })] })] }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "a" }), _jsx(_components.mi, { children: "d" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mi, { children: "b" }), _jsx(_components.mi, { children: "c" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mi, { children: "b" }), _jsx(_components.mi, { children: "d" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "10^n ac+10^{n/2}(ad+bc)+bd" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7477em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "0" }), _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.6644em" }, 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 mathnormal mtight", children: "n" }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "mord mathnormal", children: "c" }), _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: "1.138em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "0" }), _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.888em" }, 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: [_jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }), _jsx(_components.span, { className: "mord mtight", children: "/2" })] }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "mord mathnormal", children: "d" }), _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 mathnormal", children: "b" }), _jsx(_components.span, { className: "mord mathnormal", children: "c" }), _jsx(_components.span, { className: "mclose", children: ")" }), _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.6944em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "b" }), _jsx(_components.span, { className: "mord mathnormal", children: "d" })] })] })] })] }), "\n", _jsxs(_components.div, { "data-callout": true, "data-callout-type": "note", children: ["\n", _jsx(_components.div, { "data-callout-title": true, children: "Note" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsxs(_components.p, { children: ["ONLY 3 multiplications needed\nthe normal method is to calculate ", _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.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "10" }), _jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mi, { mathvariant: "normal", children: "/" }), _jsx(_components.mn, { children: "2" })] })] }), _jsx(_components.mi, { children: "a" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mi, { children: "b" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "10" }), _jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mi, { mathvariant: "normal", children: "/" }), _jsx(_components.mn, { children: "2" })] })] }), _jsx(_components.mi, { children: "c" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mi, { children: "d" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "(10^{n/2}a+b)(10^{n/2}c+d)" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.138em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "1" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "0" }), _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.888em" }, 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: [_jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }), _jsx(_components.span, { className: "mord mtight", children: "/2" })] }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mord mathnormal", children: "a" }), _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: "1.138em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "b" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "1" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "0" }), _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.888em" }, 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: [_jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }), _jsx(_components.span, { className: "mord mtight", children: "/2" })] }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mord mathnormal", children: "c" }), _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 mathnormal", children: "d" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] }), " and need 4 multiplications"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.p, { children: ["This is called ", _jsx(_components.strong, { children: "Divide and conquer" })] }), "\n", _jsxs(_components.h2, { id: "time-complexity-analysis", children: [_jsx(_components.a, { className: "heading-link", href: "#time-complexity-analysis", 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" }) }) }), "Time Complexity Analysis"] }), "\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: "M" }), _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: "M(n)" })] }) }) }), _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", style: { marginRight: "0.109em" }, children: "M" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }), ": The number of digit multiplications needed to calculate the multiplication of two numbers which have n digits respectively."] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { 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: "M" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "2" }), _jsx(_components.mn, { children: "0" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "M(2^0)=1" })] }) }) }), _jsxs(_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.109em" }, children: "M" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "2" }), _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: "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.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] })] }) }), "\n", _jsxs(_components.li, { 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: "M" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "2" }), _jsx(_components.mi, { children: "k" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "3" }), _jsx(_components.mo, { children: "⋅" }), _jsx(_components.mrow, {}), _jsx(_components.mi, { children: "M" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "2" }), _jsxs(_components.mrow, { 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: "M(2^k)=3\\cdot{} M(2^{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: "1.0991em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "M" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "2" }), _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: _jsx(_components.span, { className: "mord mathnormal mtight", style: { marginRight: "0.0315em" }, 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: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "3" }), _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: "1.0991em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "M" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "2" }), _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: [_jsx(_components.span, { className: "mord mathnormal mtight", style: { marginRight: "0.0315em" }, children: "k" }), _jsx(_components.span, { className: "mbin mtight", children: "−" }), _jsx(_components.span, { className: "mord mtight", children: "1" })] }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] }), " //Rekurrenz"] }), "\n", _jsxs(_components.li, { 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: "M" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "2" }), _jsx(_components.mi, { children: "k" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "=" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "3" }), _jsx(_components.mi, { children: "k" })] })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "M(2^k)=3^k" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_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.109em" }, children: "M" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "2" }), _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: _jsx(_components.span, { className: "mord mathnormal mtight", style: { marginRight: "0.0315em" }, 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: "0.8491em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "3" }), _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: _jsx(_components.span, { className: "mord mathnormal mtight", style: { marginRight: "0.0315em" }, children: "k" }) })] }) }) }) }) })] })] })] })] }), " // kein Beweis, für Beweis braucht man ", _jsx(_components.a, { href: "/Programming/Algorithms+%26+Data+Structures+ETH/Induction", className: "internal", "data-fs-resolved-file-path": "/Programming/Algorithms & Data Structures ETH/Induction.md", children: "Induction" }), "\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: "n" }), _jsx(_components.mo, { children: "=" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "2" }), _jsx(_components.mi, { children: "k" })] }), _jsx(_components.mo, { children: "⟹" }), _jsx(_components.mi, { children: "k" }), _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.mi, { children: "n" }), _jsx(_components.mo, { children: "⟹" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "3" }), _jsx(_components.mi, { children: "k" })] }), _jsx(_components.mo, { children: "=" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "3" }), _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.mi, { children: "n" })] })] }), _jsx(_components.mo, { 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: "3" })] })] }), _jsx(_components.mo, { children: "=" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mn, { children: "1.58" })] })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "n=2^k\\Longrightarrow k=\\log_{2}n \\Longrightarrow 3^k=3^{\\log_{2}n} = n^{\\log_{2}3}=n^{1.58}" })] }) }) }), _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: "n" }), _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.8731em", verticalAlign: "-0.024em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "2" }), _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: _jsx(_components.span, { className: "mord mathnormal mtight", style: { marginRight: "0.0315em" }, 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.6944em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0315em" }, 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.9386em", verticalAlign: "-0.2441em" } }), _jsxs(_components.span, { className: "mop", children: [_jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, 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 mathnormal", children: "n" }), _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.8491em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "3" }), _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: _jsx(_components.span, { className: "mord mathnormal mtight", style: { marginRight: "0.0315em" }, 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.8491em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "3" }), _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.0139em" }, 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 mathnormal mtight", children: "n" })] }) })] }) }) }) }) })] }), _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.8491em" } }), _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.0139em" }, 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: "3" })] }) })] }) }) }) }) })] }), _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.8141em" } }), _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: "1.58" }) }) })] }) }) }) }) })] })] })] })] }), "\n(See ", _jsx(_components.a, { href: "/Programming/Algorithms+%26+Data+Structures+ETH/Algorithm+Runtime+Analysis", className: "internal", "data-fs-resolved-file-path": "/Programming/Algorithms & Data Structures ETH/Algorithm Runtime Analysis.md", children: "Algorithm Runtime Analysis" }), ")"] }), "\n"] }), "\n", _jsxs(_components.h1, { id: "one-dimensional-goal-finding", children: [_jsx(_components.a, { className: "heading-link", href: "#one-dimensional-goal-finding", 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" }) }) }), "one dimensional goal finding"] }), "\n", _jsx(_components.p, { children: _jsx(_components.a, { href: "https://obvault-thecyberweaver.flowershow.me/Goal%20finding%20on%20a%20line.excalidraw", className: "internal new unsupported", target: "_blank", rel: "noopener noreferrer", children: "Goal finding on a line.excalidraw" }) }), "\n", _jsxs(_components.h2, { id: "time-complexity-analysis-worst-case", children: [_jsx(_components.a, { className: "heading-link", href: "#time-complexity-analysis-worst-case", 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" }) }) }), "Time Complexity Analysis (worst case)"] }), "\n", _jsxs(_components.p, { children: ["k=distance between start and end\nAnnahme: ", _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: [_jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "2" }), _jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "i" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "1" })] })] }), _jsx(_components.mo, { children: "<" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { children: "<" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "2" }), _jsx(_components.mi, { children: "i" })] })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "2^{i-1}