Give tilde approximations for the following quantities a N

Give tilde approximations for the following quantities:

a. N + 1

b. 1 + 1/N

c. (1 + 1/N )(1 + 2/N)

d. 2N³ + 15N² + N

e. lg(2N)/lg N

f. lg(N² + 1) / lg(N)

g. N¹⁰⁰/ 2^N

Please give explanations for your answers.

Solution

Tilde approximations. We use tilde approximations, where we throw away low-order terms that complicate formulas. We write ~ f(N) to represent any function that when divided by f(N) approaches 1 as N grows. We write g(N) ~ f(N) to indicate that g(N) / f(N) approaches 1 as N grows.

a. N + 1
   Tild approximations = N (N > 1)

b. 1 + 1/N
   Tild approximations = 1 (1 > 1/N)

c. (1 + 1/N )(1 + 2/N)
   = 1 + 2/N + 1/N + 2/N^2

   Tild approximations = 1 (because 1 > (2/N, 1/N, 2/N^2))

d. 2N^3 + 15N^2 + N
   Tild approximations = 2N^3 (because 2N^3 > 15N^2, N)

e. lg(2N)/lg N
   = (lg2 + lgN)/lgN (lg(xy) = lgx + lgy)
   = lg2 + 1

   Tild approximations = 1 (1 > lg2)

f. lg(N^2 + 1) / lg(N)

   Tild approximations = lg(N^2 + 1) / lg(N)

g. N^100/ 2^N
   Tild approximations = N^100/ 2^N