HW 2 Q2A

HW 2 Q2A

Bar Aschner (guest) 05 Apr 2019 12:07

Hi,
we were asked to solve t queries in time O(klogt)*(2^k+t). However, it seems that a trivial algorithm can solve this in time O(t * 2^k) by brute-forcing each challenge. What am I missing?

Re: HW 2 Q2A

Bar Aschner 05 Apr 2019 12:10

Oops, I mean't that it is easy to solve in time O(k2^k + t), by saving everything in an array.

Re: HW 2 Q2A

eliadtsf 06 Apr 2019 15:21

Such an array requires O(k * 2^k) memory space (for example, if k=60, your solution requires more than 1000 PB space!). What we meant is to use much less memory: something like O(k * t) which is much less assuming that t«2^k.

Re: HW 2 Q2A

nbitansky 06 Apr 2019 19:39

Since we didn't put any explicit requirement on space, your solutions do not have to be optimal in terms of space and then you could indeed get a slightly better solution (although the solution claimed above sounds a slightly too good —- even just comparing t k-bit strings takes k*t…).

• In general, please do not suggest solutions in the forum (before the deadline).