One important application of logarithms is found in various computer search rout

Question

One important application of logarithms is found in various computer search routines. For example, a binary search algorithm on a table (or array) of data takes a maximum of log2n (“log base 2, of n”) steps to complete, where n is the number of data elements that can be searched. How many steps (at most) are needed for a search of a table with 16 elements? 512 elements? Explain.
The approximation of the natural logarithm of 2: ln 2 ˜ 0.693 is commonly used by applied scientists, biologists, chemists, and computer scientists. For example, chemists use it to compute the half-life of decaying substances. Based on this approximation and the power rule for logarithmic expressions, how could you approximate ln 8, without a calculator? Explain

Explanation / Answer

this is called Big O notation in computer science, BigO(logn) represents logarithmic growth which increases with n, but the amount of elements that can be searched diminishes by n.

ex.) for base 2 logs, the growth only increases by one each time n doubles.
which means: if n=2 then logn=1, if n=4 then logn =2, if n=8 then logn =3,
if n=16 then logn= 4, in n=512 then logn would be 9.

some sorting algorithms in computer science are considered n2 which means that the algorithm would take 256 passes to find something in a 16 element search table, where a logn search table would only take 4 passes. an example of a logn sorting algorithm is a merge sort or a heap sort, and an n2 algorithm is a bubble sort.

hope this helps!

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

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