Question

a program p takes time proportional to log where nlogn is the input size. if the program takes 100 ms to process input of size 1,000,000, how many seconds does it take to process input of size 100

Answer 1

Answer:

The time is $4 \times 10^7 \ microseconds.$

Explanation:

$\ The \ requires \ time \ be \ t \ microseconds, \\\\\ \ formula: \\\\ time \propto \ nlog_n \Rightarrow \ time \ = \ knlogn$

$\ 10 \ = \ 100 \ log(100) \ \ \ \ \ \ \ \ \ k= 10^2 \ log\ ( \ 10^2\ ) \ k\\\\t=100,000,000 \log \ ( \ 100,000,000\ ) \ k = \ 10^8 \ log\ (\ 10^8\ )\ k \\\\\rightarrow \frac{t}{10} \ =\frac{10^8\ log \ (10^8)k}{10^2\ log\(10^2\ ) k} \\\\\rightarrow \frac{t}{10} \ =\frac{10^8\ log \ (10)\times 8 \times k}{10^2\ log\(10) \times 2 k} \\\\\rightarrow \frac{t}{10} \ =\ 4\times 10^6\\\\\rightarrow \ t \ =\ 4\times 10^6 \times 10 \\\\\rightarrow \ t \ =\ 4\times 10^7 \ microseconds$