Lesson plan
Polylogarithmic function
In mathematics, a polylogarithmic function in is a polynomial in the logarithm of , : a_k (\log n)^k + a_{k-1} (\log n)^{k-1} + \cdots + a_1(\log n) + a_0. The notation is often used as a shorthand for , analogous to for . In computer science, polylogarithmic functions occur as the order of time for some data structure operations. Additionally, the exponential function of a polylogarithmic function produces a function with quasi-polynomial growth, and algorithms with this as their time complexity are said to take quasi-polynomial time. All polylogarithmic functions of are for every exponent (for the meaning of this symbol, see small o notation), that is, a polylogarithmic function grows more slowly than any positive exponent. This observation is the basis for the soft O notation .
Article summary
In mathematics, a polylogarithmic function in is a polynomial in the logarithm of , : a_k (\log n)^k + a_{k-1} (\log n)^{k-1} + \cdots + a_1(\log n) + a_0. The notation is often used as a shorthand for , analogous to for . In computer science, polylogarithmic functions occur as the order of time for some data structure operations. Additionally, the exponential function of a polylogarithmic function produces a function with quasi-polynomial growth, and algorithms with this as their time complexity are said to take quasi-polynomial time. All polylogarithmic functions of are for every exponent (for the meaning of this symbol, see small o notation), that is, a polylogarithmic function grows more slowly than any positive exponent. This observation is the basis for the soft O notation .
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.