Mathematics
Growth of Functions
Growth of functions is a mathematical concept that deals with the rate at which a function increases as its input increases. It is used to compare the efficiency of algorithms and to determine the time complexity of algorithms. The most commonly used growth functions are logarithmic, linear, polynomial, exponential, and factorial.
Written by Perlego with AI-assistance
Related key terms
1 of 5
3 Key excerpts on "Growth of Functions"
- Lekh Raj Vermani, Shalini Vermani(Authors)
- 2019(Publication Date)
- WSPC (EUROPE)(Publisher)
Chapter 2Growth of Functions
Given a real-valued function f defined on the set of real numbers, by the growth of f we mean how rapidly or slowly it increases in comparison with another real-valued function when the real number x increases. So for the Growth of Functions, there need to be considered two functions. How rapidly or slowly the function f increases in comparison with another function g is expressed in terms of certain notations called asymptotic notations. In this chapter, we are concerned with this concept. Of course, asymptotic means that how the two functions behave only for large values of x.2.1.Introduction
Let f be a function from the set R of real numbers to R. By the growth of the function f we mean to say how the function f(x) grows when the variable x increases or becomes large. In the analysis of algorithms we are generally concerned with the number of algebraic computations involved as the running time of an algorithm is proportional to this number. The number of computations depends on the size n (which is a positive integer) of the problem instance. Thus we come across functions f : N → N, where N denotes the set of all natural numbers (or non-negative integers). Also there may be more than one algorithm for solving a certain problem so that for a given problem we may get two functions, say f(n) and g(n), giving the performance of the two algorithms (for the same problem). Which one of the two algorithms may be preferred will normally depend on the comparative growth of the two functions f(n) and g(n). In this chapter, we study this problem of comparative study of functions. A function f(n) which grows more slowly than the function g(n) is called a superior function (to g(n)). In fact we are not concerned with the growth of two functions for all n but only for large n
eBook - PDFDiscrete Mathematics
Mathematical Reasoning and Proof with Puzzles, Patterns, and Games
- Douglas E. Ensley, J. Winston Crawley(Authors)
- 2011(Publication Date)
- Wiley(Publisher)
PROOF Ask a calculus teacher and make her day! The “big-oh” notation gives a natural hierarchy of elementary functions based on their growth rates: · · · O(log 2 n) ⊆ · · · ⊆ O(n 1/3 ) ⊆ O(n 1/2 ) ⊆ O(n) ⊆ O(n 2 ) ⊆ · · · ⊆ O(2 n ) · · · We can think of each of these subset relations in its “if, then” form. For example, the relationship O(n) ⊆ O(n 2 ) can be thought of as “If f (n) ∈ O(n), then f (n) ∈ O(n 2 ).” In other words, “If f (n) grows no faster than n, then f (n) grows no faster than n 2 .” The hierarchy above says that of all the growth rates we have seen, logarith- mic growth rate is the slowest and exponential growth rate is the fastest. Although other growth rates are possible, these (and combinations of them) are sufficient for understanding our main result about the growth of recursively defined sequences. Divide-and-Conquer Recurrences A common type of recurrence relation in computer science courses arises from an- alyzing the complexity of recursive algorithms. Although these are among the most important recurrence relations for a computer scientist to understand, they are also among the most difficult to find closed formulas for. Fortunately, our function growth notation can often be used to understand the growth rate of these sequences without needing an exact closed formula. Definition A divide-and-conquer recurrence relation is one of the form a n = C · a n/ k + f (n) where C and k are positive constants (with k > 1) and f is any function on N. A typical application is the analysis of the sorting algorithm in Example 12. Before tackling this more difficult real-world example, however, we will first look at a few “abstract” examples to gain some experience with sequences like this. 4.8 Excursion: Growth of Functions 357 Example 11 The first few terms of the recursive description a n = 3 · a n/2 + n for n ≥ 2, with a 1 = 1, look like this: 1, 5, 6, 19, 20, 24, 25, .
eBook - PDF- Michail Prodan(Author)
- 2013(Publication Date)
- Pergamon(Publisher)
For example, in the life span of a tree, three growth cycles usually occur : (16) I. The development from seed to the one-year old plant (ovular cycle). II. The cycle which is determined by the roots and the first leaves. III. The cycle of the basic growth through the main phases of the life of a tree. In most cases, the first two cycles are indistinct in comparison to the third. In trees, there is also usually no clear distinction between the second and the third cycles. Periodic fluctuations of the increment in the course of a day, or in the course of a year, are not considered here. Growth functions can be established empirically or from some fundamental concept. In the first of these methods, an attempt is made to represent the course of any empirically produced curve analytically by means of a mathematical func-tion. It corresponds to curve fitting in biometrics. The curve chosen for the re-gression function must be one which appears to be both reliable and suitable. In the following section, therefore, a number of possible functions will be dis-cussed from the point of view of statistical curve fitting. From the early days of forest science, the growth functions, in increment studies, have been deduced hypothetically, despite the fact that the resulting growth curves have seldom been constructed analytically. The fundamental concept deduces hypotheses from biological, social, or economic factors and causes, which are subsequently related to growth functions. With the general progress in biology and the social sciences, such (quantitative and qualitative) concepts have gained in importance. The satisfactory solution should give the same results for both the empirical method and the fundamental concept. Growth Functions 349 22.5 Empirical Growth Functions The general characteristics of growth and increment curves suggest that a polynomial of the form : y = a + bx + ex 2 + (619) cannot suitably represent a complete growth process.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
