Algorithm Question : Please explain me(with some examples) the best/easiest way

Question

Algorithm Question: Please explain me(with some examples) the best/easiest way to find out TILDE approximation for any quantities, especially with logarithm. I've some basic idea of TILDE approximation, like big thing eats small thing, but i'm struggling to find out TILDE approximation for log expressions, or critical expressions. Please see below some examples, but basically i need to have better undertsanding of how i can easily find out the TILDE approximation for any expressions.Please explain me in details with some examples including the following quantities.

N100 / 2N ~ ?

lg(2N) / lg(N) ~ ?

lg(N2+ 1) / lg(N) ~ ?

Note: No copy/paste from Google search please. Don't attemp this question if you don't have very clear concept on this.

Explanation / Answer

Here I have some solution for Tilde approximations so far

We can use tilde approximations, where we throw away low-order terms that complicate formulas.

Some Basic rules if we follow then it will be easy to understand for you.

We can 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.

Here please follow some initial formula which will help you for better understanding

N1002Nlg(N1002N)=lg(N100)lg(2N)=100lg(N)Nlg(2)

Logarithms with different Bases

Log to the base 2 is just a constant multiple of the log to the base Log to base 2 is a (different) constant multiple of the log to any other base b, where the constant depends only on the two bases.

          log2(N) = log10(N) / log10(2)

N1002Nlg(N1002N)=lg(N100)lg(2N)=100lg(N)Nlg(2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.