LESSWRONG
LW

Computer ScienceLogic & Mathematics World Modeling
Frontpage

8

[ Question ]

What Are The Preconditions/Prerequisites for Asymptotic Analysis?

by DragonGod
3rd Feb 2023
1 min read
A
1
1

8

Computer ScienceLogic & Mathematics World Modeling
Frontpage

8

What Are The Preconditions/Prerequisites for Asymptotic Analysis?
5tailcalled
New Answer
New Comment

1 Answers sorted by
top scoring

tailcalled

Feb 03, 2023

52

Asymptotic analysis tends to be useful when you expect the function to take large values as input, but don't necessarily know how large they will be. For instance, knowing that the asymptotic complexity of sorting is O(nlogn) isn't all that useful when you are solving a list of 7 elements; it's mainly useful when considering sorting lists of 1000000000 elements (where you can infer that e.g. O(n2) would be too expensive but O(nlogn) is not).

I guess it is also sometimes useful as a sort of "interpolation strategy". Like if you want to know the properties of a function, you can first asymptotically characterize its limiting properties, and that covers a good chunk of the information about the function, leaving you only with a bounded area of uncertainty. Then you can analyze how it shifts between its asymptotes in the middle.

Add Comment
Moderation Log
More from DragonGod
View more
Curated and popular this week
A
1
0

Under what conditions is describing the behaviour of a (physical or abstract) process using asymptotic apparatus sensible/productive/reasonable?

 

Kinds of replies that I would find especially valuable:

  • Formal properties that a function (or collection thereof) must satisfy for applying asymptotic analysis to be sensible
  • Heuristics for when applying asymptotic analysis to real world processes is productive
  • Examples of real world processes satisfying the above
  • Examples of processes/functions that might seem amenable to asymptotic analysis but which it would actually be a mistake to try and consider through an asymptotic lens