"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", code: "code", h1: "h1", h5: "h5", h6: "h6", img: "img", li: "li", math: "math", mi: "mi", mn: "mn", mo: "mo", mrow: "mrow", msub: "msub", msup: "msup", mtext: "mtext", ol: "ol", p: "p", path: "path", pre: "pre", semantics: "semantics", span: "span", strong: "strong", svg: "svg", ..._provideComponents(), ...props.components }; return _jsxs(_Fragment, { children: [_jsx(_components.p, { children: _jsx(_components.a, { href: "/tags/exercise", className: "tag-pill", "data-tag": "exercise", children: "#exercise" }) }), "\n", _jsxs(_components.h1, { id: "61", children: [_jsx(_components.a, { className: "heading-link", href: "#61", 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" }) }) }), "6.1"] }), "\n", _jsxs(_components.h5, { id: "a", children: [_jsx(_components.a, { className: "heading-link", href: "#a", 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" }) }) }), "a)"] }), "\n", _jsx(_components.img, { src: "https://obvault-thecyberweaver.flowershow.me/assets/f77c3826e909b8a43e9a048d44b8aacc.jpg", alt: "f77c3826e909b8a43e9a048d44b8aacc", className: "internal", "data-fs-width": "512", "data-fs-resolved-file-path": "/assets/f77c3826e909b8a43e9a048d44b8aacc.jpg" }), "\n", _jsxs(_components.h5, { id: "b", children: [_jsx(_components.a, { className: "heading-link", href: "#b", 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" }) }) }), "b)"] }), "\n", _jsxs(_components.h1, { id: "63", children: [_jsx(_components.a, { className: "heading-link", href: "#63", 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" }) }) }), "6.3"] }), "\n", _jsx(_components.img, { src: "https://obvault-thecyberweaver.flowershow.me/assets/824628872c87d805150814384b7dc1ac.jpg", alt: "824628872c87d805150814384b7dc1ac", className: "internal", "data-fs-width": "256", "data-fs-resolved-file-path": "/assets/824628872c87d805150814384b7dc1ac.jpg" }), "\n", _jsxs(_components.h5, { id: "a-1", children: [_jsx(_components.a, { className: "heading-link", href: "#a-1", 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" }) }) }), "a)"] }), "\n", _jsx(_components.pre, { children: _jsxs(_components.code, { className: "language-auto code-highlight", children: [_jsx(_components.span, { className: "code-line", children: "A(n):\n" }), _jsx(_components.span, { className: "code-line", children: "\tif(n<=4)return n\n" }), _jsx(_components.span, { className: "code-line", children: "\treturn A(n-1)+A(n-3)+2*A(n-4)\n" })] }) }), "\n", _jsxs(_components.h5, { id: "b-1", children: [_jsx(_components.a, { className: "heading-link", href: "#b-1", 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" }) }) }), "b)"] }), "\n", _jsxs(_components.p, { children: ["Let T(n) be calls made by REC-A(n). For n≥5,\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: "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: "T" }), _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.mi, { children: "T" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "3" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mi, { children: "T" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "4" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "≥" }), _jsx(_components.mn, { children: "3" }), _jsx(_components.mo, { separator: "true", children: "⋅" }), _jsx(_components.mi, { children: "T" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "4" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T(n) ≥ T(n-1)+T(n-3)+T(n-4) ≥ 3·T(n-4)" })] }) }) }), _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.1389em" }, 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.1389em" }, children: "T" }), _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.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", style: { marginRight: "0.1389em" }, children: "T" }), _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: "3" }), _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: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _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: "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: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "3" }), _jsx(_components.span, { className: "mpunct", children: "⋅" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _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: "4" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] }), ".\nThus ", _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: "≥" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "3" }), _jsxs(_components.mrow, { children: [_jsx(_components.mo, { stretchy: "false", children: "⌊" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "4" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mi, { mathvariant: "normal", children: "/" }), _jsx(_components.mn, { children: "4" }), _jsx(_components.mo, { stretchy: "false", children: "⌋" })] })] }), _jsx(_components.mo, { children: ">" }), _jsx(_components.mi, { mathvariant: "normal", children: "Ω" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "3" }), _jsxs(_components.mrow, { children: [_jsx(_components.mn, { children: "1" }), _jsx(_components.mi, { mathvariant: "normal", children: "/" }), _jsx(_components.mn, { children: "4" })] })] }), _jsxs(_components.msup, { children: [_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) ≥ 3^{⌊(n-4)/4⌋} > Ω((3^{1/4})^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.1389em" }, 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: "0.9271em", verticalAlign: "-0.0391em" } }), _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.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: "mopen mtight", children: "⌊(" }), _jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }), _jsx(_components.span, { className: "mbin mtight", children: "−" }), _jsx(_components.span, { className: "mord mtight", children: "4" }), _jsx(_components.span, { className: "mclose mtight", children: ")" }), _jsx(_components.span, { className: "mord mtight", children: "/4" }), _jsx(_components.span, { className: "mclose mtight", 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.138em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "Ω" }), _jsx(_components.span, { className: "mopen", children: "((" }), _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.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: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "1/4" }) }) })] }) }) }) }) })] }), _jsxs(_components.span, { className: "mclose", children: [_jsx(_components.span, { className: "mclose", children: ")" }), _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: "mclose", children: ")" })] })] })] }), " with ", _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: "C" }), _jsx(_components.mo, { children: "=" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "3" }), _jsxs(_components.mrow, { children: [_jsx(_components.mn, { children: "1" }), _jsx(_components.mi, { mathvariant: "normal", children: "/" }), _jsx(_components.mn, { children: "4" })] })] }), _jsx(_components.mo, { children: "≈" }), _jsx(_components.mn, { children: "1.316" }), _jsx(_components.mo, { children: ">" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "C=3^{1/4}\\approx1.316>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.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, children: "C" }), _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.888em" } }), _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.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: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "1/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.6835em", verticalAlign: "-0.0391em" } }), _jsx(_components.span, { className: "mord", children: "1.316" }), _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.h6, { id: "another-approach", children: [_jsx(_components.a, { className: "heading-link", href: "#another-approach", 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" }) }) }), "Another approach"] }), "\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: [_jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "C" }), _jsx(_components.mi, { children: "n" })] }), _jsx(_components.mo, { children: "≥" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "C" }), _jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "1" })] })] }), _jsx(_components.mo, { children: "+" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "C" }), _jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "3" })] })] }), _jsx(_components.mo, { children: "+" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "C" }), _jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "4" })] })] }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "C^{n}\\geq C^{n-1}+C^{n-3}+C^{n-4}+O(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.8193em", verticalAlign: "-0.136em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, children: "C" }), _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 mtight", children: _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.8974em", verticalAlign: "-0.0833em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, children: "C" }), _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: _jsxs(_components.span, { className: "mord mtight", children: [_jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }), _jsx(_components.span, { className: "mbin mtight", children: "−" }), _jsx(_components.span, { className: "mord mtight", children: "1" })] }) })] }) }) }) }) })] }), _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.8974em", verticalAlign: "-0.0833em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, children: "C" }), _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: _jsxs(_components.span, { className: "mord mtight", children: [_jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }), _jsx(_components.span, { className: "mbin mtight", children: "−" }), _jsx(_components.span, { className: "mord mtight", 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: "0.8974em", verticalAlign: "-0.0833em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, children: "C" }), _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: _jsxs(_components.span, { className: "mord mtight", children: [_jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }), _jsx(_components.span, { className: "mbin mtight", children: "−" }), _jsx(_components.span, { className: "mord mtight", children: "4" })] }) })] }) }) }) }) })] }), _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", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "1" }), _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: [_jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "C" }), _jsx(_components.mn, { children: "4" })] }), _jsx(_components.mo, { children: "≥" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "C" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mi, { children: "C" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "C^{4}\\geq C^{2}+C+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.9501em", verticalAlign: "-0.136em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, children: "C" }), _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: "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.8974em", verticalAlign: "-0.0833em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, children: "C" }), _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.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.7667em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, 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: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "2" })] })] })] })] }), "\n", _jsxs(_components.h5, { id: "c", children: [_jsx(_components.a, { className: "heading-link", href: "#c", 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" }) }) }), "c)"] }), "\n", _jsx(_components.pre, { children: _jsxs(_components.code, { className: "language-auto code-highlight", children: [_jsx(_components.span, { className: "code-line", children: "M[1...n] initialized with -1\n" }), _jsx(_components.span, { className: "code-line", children: "M[1]=1; M[2]=2; M[3]=3; M[4]=4;\n" }), _jsx(_components.span, { className: "code-line", children: "MEMO-A(n, M):\n" }), _jsx(_components.span, { className: "code-line", children: " if M[n]!=-1 return M[n]\n" }), _jsx(_components.span, { className: "code-line", children: " M[n] <- MEMO-A(n-1,M) + MEMO-A(n-3,M) + 2*MEMO-A(n-4,M)\n" }), _jsx(_components.span, { className: "code-line", children: " return M[n]\n" })] }) }), "\n", _jsxs(_components.p, { children: ["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: [_jsxs(_components.mrow, { 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: "O(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.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }), "\nWith memorization one compute ", _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: _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "A" }), _jsx(_components.mi, { children: "k" })] }) }), _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: "0.8333em", verticalAlign: "-0.15em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "A" }), _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.3361em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "0em", 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 mathnormal mtight", style: { marginRight: "0.0315em" }, children: "k" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] })] }) })] }), " for each ", _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.mo, { children: "…" }), _jsx(_components.mi, { children: "n" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "k=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: "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.6444em" } }), _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" })] })] })] }), " exactly once, which gives ", _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: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(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.0278em" }, 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.h5, { id: "d", children: [_jsx(_components.a, { className: "heading-link", href: "#d", 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" }) }) }), "d)"] }), "\n", _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "DP table" }), ": one array ", _jsx(_components.code, { className: "language-auto", children: "DP[1..n]" }), ". ", _jsx(_components.code, { className: "language-auto", children: "DP[i] = A_i" }), "."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Entry formula" }), ":"] }), "\n", _jsxs(_components.li, { children: ["Base cases: ", _jsx(_components.code, { className: "language-auto", children: "DP[1]=1, DP[2]=2, DP[3]=3, DP[4]=4" }), "."] }), "\n", _jsxs(_components.li, { children: ["For ", _jsx(_components.code, { className: "language-auto", children: "i≥5" }), ": ", _jsx(_components.code, { className: "language-auto", children: "DP[i] = DP[i-1] + DP[i-3] + 2*DP[i-4]" }), "."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Order" }), ": increasing ", _jsx(_components.code, { className: "language-auto", children: "i = 5…n" }), "."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Extracting solution" }), ": return ", _jsx(_components.code, { className: "language-auto", children: "DP[n]" }), "."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Run 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: [_jsxs(_components.mrow, { 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: "O(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.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }), "\npseudo code:"] }), "\n"] }), "\n", _jsx(_components.pre, { children: _jsxs(_components.code, { className: "language-auto code-highlight", children: [_jsx(_components.span, { className: "code-line", children: "A(n):\n" }), _jsx(_components.span, { className: "code-line", children: "\tarray A[1...n]\n" }), _jsx(_components.span, { className: "code-line", children: "\tif(n<=4)return n\n" }), _jsx(_components.span, { className: "code-line", children: "\tfor i <- 5...n:\n" }), _jsx(_components.span, { className: "code-line", children: " A[i] <- A[i-1]+A[i-3]+2*A[i-4]\n" }), _jsx(_components.span, { className: "code-line", children: "\treturn A[n]\n" })] }) }), "\n", _jsxs(_components.h1, { id: "64", children: [_jsx(_components.a, { className: "heading-link", href: "#64", 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" }) }) }), "6.4"] }), "\n", _jsxs(_components.h5, { id: "a-2", children: [_jsx(_components.a, { className: "heading-link", href: "#a-2", 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" }) }) }), "a)"] }), "\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: "n" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "7" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "n=7" })] }) }) }), _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.6444em" } }), _jsx(_components.span, { className: "mord", children: "7" })] })] })] }), ", ", _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: "4" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "k=4" })] }) }) }), _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.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.6444em" } }), _jsx(_components.span, { className: "mord", children: "4" })] })] })] }), ", ", _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, { children: "=" }), _jsx(_components.mo, { stretchy: "false", children: "[" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mn, { children: "3" }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mn, { children: "4" }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mn, { children: "5" }), _jsx(_components.mo, { stretchy: "false", children: "]" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "b=[1,3,4,5]" })] }) }) }), _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", 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: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "[" }), _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", children: "3" }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _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", children: "5" }), _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: "O" }), _jsx(_components.mi, { children: "P" }), _jsx(_components.mi, { children: "T" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "OPT=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.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "P" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _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" })] })] })] }), " with ", _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: "3" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mn, { children: "4" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "7" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "3+4=7" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7278em", verticalAlign: "-0.0833em" } }), _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: "0.6444em" } }), _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: "7" })] })] })] }), "\nThe output of algorithm 1: ", _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.mn, { children: "3" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "3" })] }) }) }), _jsx(_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: "3" })] }) })] })] }), "\n", _jsxs(_components.h5, { id: "b-2", children: [_jsx(_components.a, { className: "heading-link", href: "#b-2", 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" }) }) }), "b)"] }), "\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: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "⋅" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(n\\cdot k)" })] }) }) }), _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.0278em" }, children: "O" }), _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 mathnormal", style: { marginRight: "0.0315em" }, children: "k" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] }), "\n", _jsx(_components.strong, { children: "explanation" }), ": The outer loop runs for ", _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: "=" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "N=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.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, 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.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] })] }), " to n (n iterations). For each ", _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: "N" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "N" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "N" })] }) })] }), ", the inner loop scans all ", _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.0315em" }, children: "k" })] }) })] }), " coin types and does ", _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: "(" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(1)" })] }) }) }), _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.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }), " work per coin. In total, we get ", _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: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "⋅" }), _jsx(_components.mi, { children: "k" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(n\\cdot k)" })] }) }) }), _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.0278em" }, children: "O" }), _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 mathnormal", style: { marginRight: "0.0315em" }, children: "k" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] })] }), "\n", _jsxs(_components.h5, { id: "c-1", children: [_jsx(_components.a, { className: "heading-link", href: "#c-1", 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" }) }) }), "c)"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "IH" }), ": ", _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: "f" }), _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: "f(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.1076em" }, children: "f" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }), " in the algorithm gives ", _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.mi, { children: "P" }), _jsx(_components.mi, { children: "T" }), _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: "OPT(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.0278em" }, children: "O" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "P" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }), "\n", _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: "n" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "0" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "n=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.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.6444em" } }), _jsx(_components.span, { className: "mord", children: "0" })] })] })] }), "\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: "f" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mn, { children: "0" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "0" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "f(0)=0" })] }) }) }), _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.1076em" }, children: "f" }), _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.6444em" } }), _jsx(_components.span, { className: "mord", children: "0" })] })] })] }), "\nthis is true because if the total value is 0, then we need no coins\n", _jsx(_components.strong, { children: "IS" }), ": Assume ", _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: "f" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mtext, { children: " " }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "∈" }), _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.annotation, { encoding: "application/x-tex", children: "f(n),\\; n\\in[N-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.1076em" }, children: "f" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _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: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, 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: "]" })] })] })] }), " are already computed.\nWe can then obtain the best choosing strategy (", _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.mi, { children: "P" }), _jsx(_components.mi, { children: "T" }), _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: "OPT(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.0278em" }, children: "O" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "P" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "N" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }), ") by selecting one coin and a optimal choosing strategy from ", _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.mi, { children: "P" }), _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, { separator: "true", children: "," }), _jsx(_components.mtext, { children: " " }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "∈" }), _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.annotation, { encoding: "application/x-tex", children: "OPT(n),\\; n\\in[N-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.0278em" }, children: "O" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "P" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, 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: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _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: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "[" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, 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: "]" })] })] })] }), " (which is determined by the coin we chose). The algorithm iterate through all possible coins and finds the choosing strategy with least coins. Thus, after each outer iteration, ", _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: "f" }), _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: "f(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.1076em" }, children: "f" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }), " must have the value of ", _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.mi, { children: "P" }), _jsx(_components.mi, { children: "T" }), _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: "OPT(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.0278em" }, children: "O" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "P" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] })] }), "\n", _jsxs(_components.h5, { id: "d-1", children: [_jsx(_components.a, { className: "heading-link", href: "#d-1", 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" }) }) }), "d)"] }), "\n", _jsx(_components.pre, { children: _jsxs(_components.code, { className: "language-auto code-highlight", children: [_jsx(_components.span, { className: "code-line", children: "array f[0...n] <- undefined\n" }), _jsx(_components.span, { className: "code-line", children: "f[0] <- 0\n" }), _jsx(_components.span, { className: "code-line", children: "findOPT(n):\n" }), _jsx(_components.span, { className: "code-line", children: "\tif f[n] is undefined then\n" }), _jsx(_components.span, { className: "code-line", children: " return f[n]\n" }), _jsx(_components.span, { className: "code-line", children: "\tbest <- INF\n" }), _jsx(_components.span, { className: "code-line", children: "\tfor i <- 1...k do\n" }), _jsx(_components.span, { className: "code-line", children: " if b[i]<=n then\n" }), _jsx(_components.span, { className: "code-line", children: " best <- min(best, 1 + findOPT(n − b[i]))\n" }), _jsx(_components.span, { className: "code-line", children: "\tf[n] <- best\n" }), _jsx(_components.span, { className: "code-line", children: "\treturn f[n]\n" }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsx(_components.span, { className: "code-line", children: "Print(findOPT(N))\n" })] }) })] }); } function MDXContent(props = {}) { const {wrapper: MDXLayout} = { ..._provideComponents(), ...props.components }; return MDXLayout ? _jsx(MDXLayout, { ...props, children: _jsx(_createMdxContent, { ...props }) }) : _createMdxContent(props); } return { default: MDXContent };

Links to this page: