Examples
All the commonly used functions f(n) (such as n, nk, 2n) are time- and space-constructible, as long as f(n) is at least cn for a constant c > 0. No function which is o(n) can be time-constructible unless it is eventually constant, since there is insufficient time to read the entire input. However, log(n) is a space-constructible function.
Read more about this topic: Constructible Function
Famous quotes containing the word examples:
“It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
—G.C. (Georg Christoph)
“In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.”
—Michel de Montaigne (1533–1592)
“No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
—André Breton (1896–1966)