in Algorithms recategorized by
413 views
6 votes
6 votes

A computer program computes a function $\: f \: \{0, 1\}^* \times \{0, 1\}^* \rightarrow \{0, 1\}^*$. Suppose $f(a, b)$ ahs length $\mid b \mid ^2$, where $\mid a \mid$ and $\mid b \mid$ are the lengths of $a$ and $b$. Suppose, using this program, the following computation is performed.

x="01"
for i=1, ... , n do
    x=f("01", x)

Suppose at the end, the length of the string $x$ is $t$. Which of the following is TRUE (assume $n \geq 10)?$

  1. $ t \leq 2n$
  2. $n < t \leq n^2$
  3. $n^2 < t \leq n^{\log_2 n}$
  4. $ n^{\log_2 n} < t \leq 2^{(2n)}$
  5. $2^{(2n)} < t$
in Algorithms recategorized by
413 views

3 Comments

How lower limit.? Shouldn't t exactly be $2^{2n}$ when $f(a,b)$ is exact?
0
0

Please check the options: (options are wrong in above question)

0
0

@jothee  mam or @Arjun Sir please correct option D. Upper bound should be 2^(2^n), not 2^(2*n).

0
0

1 Answer

0 votes
0 votes
Initially $x$ is of $2$ bits.

In next iteration of loop $x$ has size $4$

lly, after $n$ iterations(at the end of loop ) the size of $x$ is $2^{(2*2*2*2*.......n \space times)}$

ie, $t=2^{2^n}$

option $A, B, C$ is wrong as they are small compared to $t$.

option $E$ is wrong as it exceeds the value of $t$.

So, answer is option $D$
edited by
Answer:

Related questions