3.2 The growth of functions

Question 1

The time required to solve a
problem depends on?
and how we can we find how time requires is affected by what it depends on?

Answer 1

1. number of operations it uses
2. The hardware and software used to run the program that implements the algorithm.

We can closely approximate the time required to solve a problem of size n by multiplying the previous time
required by a constant. For example, on a supercomputer, we might be able to solve a problem
of size n a million times faster than we can on a PC. However, this factor of one million will
not depend on n (except perhaps in some minor ways).

Question 2

The growth of functions is often described using a special notation. Describe it:

Answer 2

Let f and g be functions from the set of integers or the set of real numbers to the set of real
numbers. We say that f(x) is O(g(x)) if there are constants C and k such that
|f(x)| ≤ C|g(x)|
whenever x > k. [This is read as “f(x) is big-oh of g(x).”]

Remark: Intuitively, the definition that f(x) is O(g(x)) says that f(x) grows slower than some
fixed multiple of g(x) as x grows without bound.

Question 3

What are the constants C and k in the definition of big-O notation :
and their need in Big O:

Answer 3

They are witnesses to the relationship f(x) is O(g(x)).

To establish that f(x) is O(g(x)) we need only one pair of witnesses to
this relationship. That is, to show that f(x) is O(g(x)), we need find only one pair of constants C Assessment and k, the witnesses, such that |f(x)| ≤ C|g(x)| whenever x > k.

Question 4

How many pair of witnesses to the relationship f(x) is O(g(x))?

Answer 4

Note that when there is one pair of witnesses to the relationship f(x) is O(g(x)), there are
infinitely many pairs of witnesses. To see this, note that if C and k are one pair of witnesses,
then any pair C′ and k′, where C < C′ and k < k′, is also a pair of witnesses, because
|f(x)| ≤ C|g(x)| ≤ C′|g(x)| whenever x > k′ > k

Question 5

Big-O symbol is also called :

Answer 5

The big-O symbol is sometimes called

a Landau symbol after the German mathematician Edmund Landau.

Question 6

WORKING WITH THE DEFINITION OF BIG-O NOTATION:

Answer 6

A useful approach for finding a pair of witnesses is to first select a value of k for which the size of |f(x)| can be readily
estimated when x > k and to see whether we can use this estimate to find a value of C for which
|f(x)| ≤ C|g(x)| for x > k.

See the figure 2, 220 page.

Question 7

When are 2 functions of Same Order?

Answer 7

Note that in Example 1 we have two functions, f(x) = x2 + 2x + 1 and g(x) = x2, such
that f(x) is O(g(x)) and g(x) is O(f(x))—the latter fact following from the inequality
x2 ≤ x2 + 2x + 1, which holds for all nonnegative real numbers x. We say that two functions f(x) and g(x) that satisfy both of these big-O relationships are of the same order

Question 8

Represent f(x) is O(g(x)) in math symbols:

Answer 8

The fact that f(x) is O(g(x)) is sometimes written f(x) = O(g(x)). However, the equals
sign in this notation does not represent a genuine equality. Rather, this notation tells us that an
inequality holds relating the values of the functions f and g for sufficiently large numbers in the
domains of these functions. However, it is acceptable to write f(x) ∈ O(g(x)) because O(g(x))
represents the set of functions that are O(g(x)).

Question 9

When f(x) is O(g(x)), and h(x) is a function that has larger absolute values than g(x)

What are we allowed with Big O notation.

Answer 9

When f(x) is O(g(x)), and h(x) is a function that has larger absolute values than g(x) does
for sufficiently large values of x, it follows that f(x) is O(h(x)). In other words, the function g(x)
in the relationship f(x) is O(g(x)) can be replaced by a function with larger absolute values. To
see this, note that if
| f(x)| ≤ C|g(x)| if x > k,
and if |h(x)| > |g(x)| for all x > k, then
| f(x)| ≤ C|h(x)| if x > k.
Hence, f(x) is O(h(x))

Question 10

How to chose g function in Big O notation:

Answer 10

When big-O notation is used, the function g in the relationship f(x) is O(g(x)) is often chosen
to have the smallest growth rate of the functions belonging to a set of reference functions, such
as functions of the form xn, where n is a positive real number

Question 11

how big-O notation is used to estimate the growth of functions?

Answer 11

Example 2 illustrates how big-O notation is used to estimate the growth of functions

Question 12

Illustrate how to show that a big-O relationship does not hold:
Show that n2 is not O(n).

Answer 12

To show that n2 is not O(n), we must show that no pair of witnesses C and k exist such
that n2 ≤ Cn whenever n > k. We will use a proof by contradiction to show this.
Suppose that there are constants C and k for which n2 ≤ Cn whenever n > k. Observe that
when n > 0 we can divide both sides of the inequality n2 ≤ Cn by n to obtain the equivalent
inequality n ≤ C. However, no matter what C and k are, the inequality n ≤ C cannot hold for
all n with n > k. In particular, once we set a value of k, we see that when n is larger than the
maximum of k and C, it is not true that n ≤ C even though n > k. This contradiction shows that
n2 is not O(n).

Question 13

Polynomials can often be used to estimate the growth of functions. Instead of analyzing the
growth of polynomials each time they occur, we would like a result that can always be used
to estimate the growth of a polynomial. Theorem?

Prove it:

Answer 13

Let f(x) = anx^n + an−1x^(n−1) + ⋯ + a1x + a0, where a0, a1, … , an−1, an are real numbers. Then
f(x) is O(x^n).

It shows that the leading term
of a polynomial dominates its growth by asserting that a polynomial of degree n or less
is O(xn).

Question 14

Give big-O estimates for the factorial function and the logarithm of the factorial function,

Answer 14

A big-O estimate for n! can be obtained by noting that each term in the product does
not exceed n. Hence,
n! = 1 ⋅ 2 ⋅ 3 ⋅⋯⋅ n
≤ n ⋅ n ⋅ n ⋅⋯⋅ n
= nn.
This inequality shows that n! is O(nn), taking C = 1 and k = 1 as witnesses. Taking logarithms
of both sides of the inequality established for n!, we obtain
log n! ≤ log nn = n log n.
This implies that log n! is O(n log n), again taking C = 1 and k = 1 as witnesses.

Question 15

Frequently used functions in order:

Answer 15

1, log n, n, n log n, n2, 2n, n!

Using calculus it can be shown that each function in the list is smaller than the succeeding
function, in the sense that the ratio of a function and the succeeding function tends to zero as n
grows without bound.
Fig Page 223.

DOUBT:
using a scale for the values
of the functions that doubles for each successive marking on the graph. That is, the vertical scale
in this graph is logarithmic.

Question 16

USEFUL BIG-O ESTIMATES INVOLVING POWERS:

Answer 16

if f(n) is a polynomial of degree d or less,
then f(n) is O(nd).
d > c > 1, then nc is O(n^d)
but nd is not O(n^c).

Question 17

USEFUL BIG-O ESTIMATES INVOLVING powers of log:

Answer 17

every positive power of the logarithm of n to the base b, where b > 1, is big-O of every positive power of n, but the reverse relationship never holds.

(logb n)^c is O(n^d), but n^d is not (O(logb n)^c)

as logb n is O(n) whenever b > 1

Question 18

USEFUL BIG-O ESTIMATES INVOLVING Exponentials and Powers:

Answer 18

Since n is O(2^n). whenever d is +ve, b > 1:
n^d is O(b^n), but b^n is not O(n^d).

Every power of n is big-O of every exponential function of n with a base that
is greater than one, but the reverse relationship never holds.

Question 19

USEFUL BIG-O ESTIMATES INVOLVING Exponentials :

Answer 19

when c > b > 1,
b^n is O(c^n), but c^n is not O(b^n).

If we have two exponential functions with different bases greater than one, one
of these functions is big-O of the other if and only if its base is smaller or equal

Question 20

USEFUL BIG-O ESTIMATES INVOLVING POWERS and FACTORIAL:

Answer 20

if c > 1, we have

c^n is O(n!), but n! is not O(c^n).

Question 21

The Growth of Combinations of Functions

Addition of funcs:

Its Theorem and Corollary:

Answer 21

Suppose that f1(x) is O(g1(x)) and that f2(x) is O(g2(x)). Then ( f1 + f2)(x) is O(g(x)), where
g(x) = (max(|g1(x)|, |g2(x)|) for all x.

Prove it too, page 225.
What happens to witnesses?

C = C1 + C2
k = max(k1,k2)

|( f1 + f2)(x)| ≤ C|g(x)| whenever x > k

Corollary:
Suppose that f1(x) and f2(x) are both O(g(x)).
Then ( f1 + f2)(x) is O(g(x)).

Question 22

The Growth of Combinations of Functions

For Product:

Answer 22

Suppose that f1(x) is O(g1(x)) and f2(x) is O(g2(x)).
Then ( f1f2)(x) is O(g1(x)g2(x)).

C = C1C2 and k = max(k1, k2), such that
|( f1f2)(x)| ≤ C|g1(x)g2(x)|
whenever x > k

Question 23

Big-Omega

Answer 23

Let f and g be functions from the set of integers or the set of real numbers to the set of real
numbers. We say that f(x) is Ω(g(x)) if there are constants C and k with C positive such that
|f(x)| ≥ C|g(x)|
whenever x > k.
[This is read as “f(x) is big-Omega of g(x).”]

f(x) is Ω(g(x)) if and only if g(x) is O(f(x))

Question 24

When is upper and lower bound both requires? Its solution?

Answer 24

Knowing the order of growth requires that we have both an upper bound and a lower bound for the size
of the function. 
That is, given a function f(x), we want a reference function g(x) such that f(x)
is O(g(x)) and f(x) is Ω(g(x)).

Big-Theta notation is used to express both of
these relationships, providing both an upper and a lower bound on the size of a function.

Question 25

Big-Theta notation

1. Defintition
2. What do we call it, say..
3. Equivalence.. Big O relations..
4. THe inequality of it, witnesses.
5. Big Omega
6. Usually what’s f(x)’s and g(x)’s complexity?

Answer 25

1.Let f and g be functions from the set of integers or the set of real numbers to the set of
real numbers. We say that f(x) is Θ(g(x)) if f(x) is O(g(x)) and f(x) is Ω(g(x)). When f(x) is
Θ(g(x)),
2.we say that f is big-Theta of g(x), that f(x) is of order g(x), and that f(x) and g(x)
are of the same order.

3.When f(x) is Θ(g(x)), it is also the case that g(x) is Θ( f(x)). Also note that f(x) is Θ(g(x)) if
and only if f(x) is O(g(x)) and g(x) is O( f(x))

4.Note that f(x) is
Θ(g(x)) if and only if there are positive real numbers C1 and C2 and a positive real number k
such that
C1|g(x)| ≤ | f(x)| ≤ C2|g(x)|
whenever x > k. 

5.The existence of the constants C1, C2, and k tells us that f(x) is Ω(g(x)) and that f(x) is O(g(x)), respectively.

6.Usually, when big-Theta notation is used, the function g(x) in Θ(g(x)) is a relatively simple
reference function, such as xn, cx, log x, and so on, while f(x) can be relatively complicated.

Question 26

Theorem for Order of polynomial

Answer 26

Let f(x) = anx^n + an−1x^(n−1) + ⋯ + a1x + a0, where a0, a1, … , an are real numbers with
an ≠ 0. Then f(x) is of order x^n.

One useful fact is that the leading term of a polynomial determines its order. For example,
if f(x) = 3x5 + x4 + 17x3 + 2, then f(x) is of order x5