MadeEasy Subject Test: Algorithms - Time Complexity

Question

for an O(log n) algorithum , x takes 12 second to execute his data Y runs the same algorithum on same machine and it took him 20 sec for data size 32 the data size of X is ????

Answer 1

Let size of X data  = n

So, C1.log(base2) n = 12---------------(1)

C1.log(base2) 32 = 20----------(2)

solving (2) C1*(5) = 20                 (here log(base 2) 32) evalautes to 5 as (2^5=32))

so C1 = 4

Put value of C1 in (1)

log(base2) n = 12/4

log(base2)n = 3

so n  =(2^3) = 8

Ans: 8

Comments

@anonymous, can u please tell why have u taken d absolute value??D rest method is understandable. log|x|. Rest method is K. :)

Answer 2

O(log n) => t = c*log n

For X, 12 = c*log (|X|)

For Y, 20 = c*log 32

So, $\frac{12}{20} = \frac{log(|X|)}{log(32)}$

=> $\frac{3}{5} = \frac{log(|X|)}5$

=> $log(|X|) = 3$

=> |X| = 8

Answer 3

Let the size of X data be $n$.

So,

$c \log_{2} n = 12$

for some constant $c > 0$.

Now, we know that Y has a data of $32$ elements and gets the output in $20 s$, so,

$c \log_{2} 32 = 20$

which gives: $c = 4$.

So, putting value of $c$ in first equation,

$4 \log_{2} n = 12$

$\Rightarrow \log_{2} n = \frac {12}{4}$

$\Rightarrow n = 2^{3}$

$\Rightarrow n = 8$.

$Answer = 8.$