{
localUrl: '../page/78l.html',
arbitalUrl: 'https://arbital.com/p/78l',
rawJsonUrl: '../raw/78l.json',
likeableId: '0',
likeableType: 'page',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
pageId: '78l',
edit: '13',
editSummary: '',
prevEdit: '12',
currentEdit: '13',
wasPublished: 'true',
type: 'wiki',
title: 'Asymptotic Notation',
clickbait: 'Asymptotic notation seeks to capture the behavior of functions as its input(s) become extreme. It is most widely used in Computer Science and Numerical Approximation.',
textLength: '8668',
alias: '78l',
externalUrl: '',
sortChildrenBy: 'likes',
hasVote: 'false',
voteType: '',
votesAnonymous: 'false',
editCreatorId: 'MorganRedding',
editCreatedAt: '2017-01-10 03:25:06',
pageCreatorId: 'MorganRedding',
pageCreatedAt: '2017-01-05 17:33:53',
seeDomainId: '0',
editDomainId: '2193',
submitToDomainId: '0',
isAutosave: 'false',
isSnapshot: 'false',
isLiveEdit: 'true',
isMinorEdit: 'false',
indirectTeacher: 'false',
todoCount: '0',
isEditorComment: 'false',
isApprovedComment: 'false',
isResolved: 'false',
snapshotText: '',
anchorContext: '',
anchorText: '',
anchorOffset: '0',
mergedInto: '',
isDeleted: 'false',
viewCount: '28',
text: 'Asymptotic Notation (Bachmann–Landau notation) is a notation for comparing the behavior of functions at extreme values – both very large, and very small. This is a convenient way to compare the performance of algorithms on large inputs, as well as the accuracy of approximations. This page will focus on the behavior at very large values, which is useful for analyzing the behavior of algorithms (both time and space requirements), rather than very minute values.\n\nThis notation is intended for functions that are always non-negative or, at least, tend towards a non-negative value.\n\n## Asymptotic Behavior ##\n\nThe asymptotic behavior of a function is its behavior as its input grows large.\n\n\\\n\nFor example, as x grows large, the three functions above all start to take on the same asymptotic behavior. Asymptotic notation gives a way to express the relationship between two functions' asymptotic behaviors.\n\n## Little-Oh ##\n\nSuppose we have two functions f(x) and g(x), such that\n\n$$\\lim_{x \\rightarrow \\infty} \\frac{f(x)}{g(x)} = 0$$\n\nThen we say that $f(x) = o(g(x))$ (spoken as "f is little oh of g"), which, colloquially, means that $g(x)$ grows much faster than $f(x)$ in the long run (i.e. for large values of $x$).\n\nFor example, consider $f(x) = x$ and $g(x) = x^2$. Because $\\lim_{x \\rightarrow \\infty} \\frac{x}{x^2} = 0$, we know $x = o(x^2)$. Therefore $x^2$ will not only eventually overtake $x$, and will become arbitrarily large relative to $x$. In other words, we can make $\\frac{g(x)}{f(x)}$ (or $g(x) - f(x)$) become as large as we want by finding a sufficiently large $x$ value.\n\n### A Note on Notation ###\n\nWhile the standard notation uses an equal sign (i.e. $f(x) = o(g(x))$), a more precise notation might be $f(x) \\in o(g(x))$, where $o(g(x))$ is the set of functions that are asymptotically dominated by $g(x)$. Nonetheless, using an equal sign is customary, and is the notation that will be used on this page.\n\n## Examples ##\n\nThis section contains examples of how one may determine the asymptotic relationship of two functions using L'Hôpital's Rule.\n\n### Example 1 ###\n\nConsider $f(x) = 200x + 10000$ and $g(x) = x^2$. Prove that $f(x) = o(g(x))$.\n\n\n\nFrom the graph, we can guess that $f(x) = o(g(x))$, because (it appears) that for large values of $x$, $g(x) > f(x)$. To prove this, it suffices to prove that:\n\n$$\\lim_{x \\rightarrow \\infty} \\frac{f(x)}{g(x)} = \\lim{x \\rightarrow \\infty} \\frac{200x + 10000}{x^2} = 0$$\n\nUsing L'Hôpital's Rule, we have:\n\n$$\\lim_{x \\rightarrow \\infty} \\frac{200x + 10000}{x^2} = \\lim_{x \\rightarrow \\infty} \\frac{200}{2x}$$\n\nWhich is zero; therefore our original guess was correct, and $f(x) = o(g(x))$.\n\n### Example 2 ###\n\nLet $f(x) = 20x^2 - 10x + 5$ and $g(x) = 2x^2 - x + 10$.\n\n\n\nFrom the graph, we can guess that $g(x) = o(f(x))$. To verify this, we will again evaluate the limit with L'Hôpital's Rule:\n\n$$\\lim_{x \\rightarrow \\infty} \\frac{g(x)}{f(x)} = \\lim_{x \\rightarrow \\infty} \\frac{2x^2 - x + 10}{20x^2 - 10x + 5} = \\lim_{x \\rightarrow \\infty} \\frac{4x - 1}{40x - 10}$$\n\nUnlike the previous example, applying L'Hôpital's Rule doesn't seem to have reduced the fraction to an easily evaluable limit. Fortunately, we are welcome to apply L'Hôpital's Rule as many times as we like, without changing the value of the limit:\n\n$$= \\lim_{x \\rightarrow \\infty} \\frac{4}{40} = \\frac{1}{10}$$\n\nThis is *not* zero, and so our guess was wrong: $f(x)$ is *not* dominated by $g(x)$. If we apply the same test but with $f(x)$ on top and $g(x)$ on the bottom to also verify that $g(x) \\neq o(f(x))$.\n\n## Properties of Little-Oh ##\n\nAn equivalent definition for $f(x) = o(g(x))$ is:\n\n$$\\forall_{c>0} \\exists_{n>0} \\text{ such that } \\forall_{x>n} c \\cdot f(x) \\leq g(x)$$\n\nIn other words $g(x)$ will eventually overtake $f(x)$, no matter how much you scale $f(x)$ by. From our first example, we showed that $200 x + 10000 = o(x^2)$. This means that, no matter what $c$ you pick, $c(200x + 10000)$ will eventually be overtaken by $x^2$ – it's just a matter of finding a big enough $n$.\n\nLittle-oh has the following properties:\n\n 1. $f(x) = o(f(x))$ is always false\n 2. $f(x) = o(g(x))\\ \\ \\implies\\ \\ g(x) \\neq o(f(x))$\n 3. $f(x) = o(g(x)) \\text{ and } g(x) = o(h(x))\\ \\ \\implies\\ \\ f(x)= o(h(x))$\n 4. $f(x) = o(g(x))\\ \\ \\implies\\ \\ c + f(x) = o(g(x))$\n 5. $f(x) = o(g(x))\\ \\ \\implies\\ \\ c \\cdot f(x) = o(g(x))$\n\nThe first three properties are essentially the same properties required of a strict ordering, which means that this notation gives us a way to order functions by how quickly they grow (see the "Common Functions" section). Indeed, little-oh is often thought of as a "less than" sign that compares functions via their asymptotic behavior.\n\nThe 4th and 5th properties show that asymptotic notation is independent of constant factors or shifts. This is useful in computer science, where such constants may vary by hardware, programming language, and other variables that are often hard to talk about precisely; asymptotic notation gives computer scientists a way to analyze algorithms independent of the hardware that is running it.\n\n## Common Functions ##\n\nFunctions that are frequently seen while analyzing algorithms are of particular use and interest. Because little-Oh notation suggests a strict ordering, the following functions are listed from smallest to largest, asymptotically.\n\n 1. $f(x) = 1$\n 2. $f(x) = log(log(x))$\n 3. $f(x) = log(x)$\n 4. $f(x) = x$\n 5. $f(x) = x \\cdot log(x)$\n 6. $f(x) = x^{1+\\epsilon}$, $0 < \\epsilon < 1$\n 7. $f(x) = x^2$\n 8. $f(x) = x^3$\n 9. $f(x) = x^4$\n 10. ...\n 11. $f(x) = e^{cx}$\n 12. $f(x) = x!$\n\n## Theta, Omega, and Big-Oh ##\n\n### Theta and Little-Omega###\n\nGiven that there exists notation for representing the relationship between two functions if $\\lim_{x \\rightarrow \\infty} \\frac{f(x)}{g(x)} = 0$, it seems natural to extend this notation to the other two cases: namely when the limit equals infinity, and when the limit equals a (positive) constant.\n\nWhen $0 < \\lim_{x \\rightarrow \\infty} \\frac{f(x)}{g(x)} < \\infty$, we say $f(x) = \\Theta(g(x))$ (pronounced "f is theta of g").\n\nWhen $\\lim_{x \\rightarrow \\infty} \\frac{f(x)}{g(x)} = \\infty$, we say $f(x) = \\omega(g(x))$ (pronounced "f is little omega of g").\n\nLittle-omega is a natural complement to little-oh: if $f(x) = o(g(x))$, then $g(x) = \\omega(f(x))$.\n\nFor any function $g(x)$, little-oh, little-omega, and Theta are disjoint sets. That is, $f(x)$ is either $o(g(x))$, $\\Theta(g(x))$, or $\\omega(g(x))$, but cannot be more than one.\n\n### Big-Oh and Big-Omega ###\n\nThough little-oh and little-omega offer a strict ordering, they are less used than their bigger siblings: big-oh and big-omega.\n\n$f(x) = O(g(x))$ if $f(x) = o(g(x))$ or $f(x) = \\Theta(g(x))$, and, similarly, $f(x) = \\Omega(g(x))$ if $f(x) = \\omega(g(x))$ or $f(x) = \\Theta(g(x))$.\n\n## Use in Computer Science ##\n\nIn Computer Science, algorithms have runtimes, which are functions that take the size of their input and return (approximately) how long the algorithm will need to run. Big-Oh, in particular, sees widespread use, and it is standard practice that an algorithm's runtime be given using asymptotic notation.\n\nFor example, the algorithm mergesort (an algorithm that sorts a list of numbers) requires $\\Theta(n\\ lg(n))$ time. This suggests that running the algorithm on a list with 1024 elements will take roughly 2.2 times longer than on a list with 512 elements.\n\nIn contrast, insertionsort (an algorithm that also sorts lists of numbers) runs in $\\Theta(n^2)$ time. This suggests that bubble sort will run roughly 4 times longer on a list with 1024 elements than on a list with 512.\n\nHere, we can use the simplified runtimes ($n\\ lg(n)$ and $n^2$) to still make useful comparisons between the algorithms. In particular, as the size of the list gets large, we can expect the mergesort to eventually outperform insertionsort, because $n lg(n) = o(n^2)$.\n\nUnfortunately, an algorithm's runtime often depends on more than just the size of the input, but on the particular flavor as well. For instance, some sorting algorithms behave very poorly on lists that are completely reserved (e.g. $[6,5,4,3,2,1]$) but very well on lists that are nearly sorted to begin with (e.g. $[1,2,3,4,6,5]$). Typically the worst-case (i.e. slowest) performance is used to determine the asymptotic behavior of the function. For instance, though bubble sort (another sorting algorithm) *can* run in $n$ time, in the worst-case scenario it requires $n^2$ time, though classifying it as an $O(n^2)$ algorithm.',
metaText: '',
isTextLoaded: 'true',
isSubscribedToDiscussion: 'false',
isSubscribedToUser: 'false',
isSubscribedAsMaintainer: 'false',
discussionSubscriberCount: '1',
maintainerCount: '1',
userSubscriberCount: '0',
lastVisit: '',
hasDraft: 'false',
votes: [],
voteSummary: 'null',
muVoteSummary: '0',
voteScaling: '0',
currentUserVote: '-2',
voteCount: '0',
lockedVoteType: '',
maxEditEver: '0',
redLinkCount: '0',
lockedBy: '',
lockedUntil: '',
nextPageId: '',
prevPageId: '',
usedAsMastery: 'false',
proposalEditNum: '0',
permissions: {
edit: {
has: 'false',
reason: 'You don't have domain permission to edit this page'
},
proposeEdit: {
has: 'true',
reason: ''
},
delete: {
has: 'false',
reason: 'You don't have domain permission to delete this page'
},
comment: {
has: 'false',
reason: 'You can't comment in this domain because you are not a member'
},
proposeComment: {
has: 'true',
reason: ''
}
},
summaries: {},
creatorIds: [
'MorganRedding'
],
childIds: [],
parentIds: [],
commentIds: [],
questionIds: [],
tagIds: [
'work_in_progress_meta_tag'
],
relatedIds: [],
markIds: [],
explanations: [],
learnMore: [],
requirements: [
{
id: '7211',
parentId: 'derivative_calculus',
childId: '78l',
type: 'requirement',
creatorId: 'MorganRedding',
createdAt: '2017-01-09 18:45:01',
level: '2',
isStrong: 'true',
everPublished: 'true'
}
],
subjects: [],
lenses: [],
lensParentId: '',
pathPages: [],
learnMoreTaughtMap: {},
learnMoreCoveredMap: {},
learnMoreRequiredMap: {},
editHistory: {},
domainSubmissions: {},
answers: [],
answerCount: '0',
commentCount: '0',
newCommentCount: '0',
linkedMarkCount: '0',
changeLogs: [
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21570',
pageId: '78l',
userId: 'MorganRedding',
edit: '13',
type: 'newEdit',
createdAt: '2017-01-10 03:25:06',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21569',
pageId: '78l',
userId: 'MorganRedding',
edit: '12',
type: 'newEdit',
createdAt: '2017-01-10 03:20:37',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21384',
pageId: '78l',
userId: 'MorganRedding',
edit: '11',
type: 'newEdit',
createdAt: '2017-01-10 01:28:11',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21383',
pageId: '78l',
userId: 'MorganRedding',
edit: '10',
type: 'newEdit',
createdAt: '2017-01-10 01:26:32',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21382',
pageId: '78l',
userId: 'MorganRedding',
edit: '9',
type: 'newEdit',
createdAt: '2017-01-10 01:19:31',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21379',
pageId: '78l',
userId: 'MorganRedding',
edit: '0',
type: 'newTag',
createdAt: '2017-01-09 19:48:08',
auxPageId: 'work_in_progress_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21378',
pageId: '78l',
userId: 'MorganRedding',
edit: '8',
type: 'newEdit',
createdAt: '2017-01-09 19:48:07',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21377',
pageId: '78l',
userId: 'MorganRedding',
edit: '0',
type: 'newRequirement',
createdAt: '2017-01-09 18:56:23',
auxPageId: 'derivative_calculus',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21376',
pageId: '78l',
userId: 'MorganRedding',
edit: '7',
type: 'newEdit',
createdAt: '2017-01-09 18:56:21',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21375',
pageId: '78l',
userId: 'MorganRedding',
edit: '0',
type: 'deleteTag',
createdAt: '2017-01-09 18:44:35',
auxPageId: 'work_in_progress_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21373',
pageId: '78l',
userId: 'MorganRedding',
edit: '6',
type: 'newEdit',
createdAt: '2017-01-09 18:34:19',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21349',
pageId: '78l',
userId: 'MorganRedding',
edit: '5',
type: 'newEdit',
createdAt: '2017-01-06 03:45:18',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21348',
pageId: '78l',
userId: 'MorganRedding',
edit: '4',
type: 'newEdit',
createdAt: '2017-01-06 00:53:05',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21343',
pageId: '78l',
userId: 'MorganRedding',
edit: '0',
type: 'newTag',
createdAt: '2017-01-05 20:02:46',
auxPageId: 'work_in_progress_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21342',
pageId: '78l',
userId: 'MorganRedding',
edit: '3',
type: 'newEdit',
createdAt: '2017-01-05 20:02:45',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21341',
pageId: '78l',
userId: 'MorganRedding',
edit: '2',
type: 'newEdit',
createdAt: '2017-01-05 20:00:20',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '21340',
pageId: '78l',
userId: 'MorganRedding',
edit: '1',
type: 'newEdit',
createdAt: '2017-01-05 17:33:53',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
}
],
feedSubmissions: [],
searchStrings: {},
hasChildren: 'false',
hasParents: 'false',
redAliases: {},
improvementTagIds: [],
nonMetaTagIds: [],
todos: [],
slowDownMap: 'null',
speedUpMap: 'null',
arcPageIds: 'null',
contentRequests: {}
}