(a) In a certain game you can collect points. The first day you collect 1, the n
ID: 3884610 • Letter: #
Question
(a) In a certain game you can collect points. The first day you collect 1, the next day you can collect 2, the third day you collect 4, ... Each day you double the amount compared to the earlier day. In how many days till you have collected in total 2,147,483,647 • How many bits does it take to represent 2,147,483,647?
(b) you have accumulated 2,147,483,647 points. Lets say now every time you lose, the number of points you have decreases by a factor of 2. (i.e. if you have 8 points and you lose, you now have 4 points and so on.) If you fight every day and lose, how many days till you lose the game? If you started with N points, how many days till you have no points?
(c) You have three algorithms, A took O(n^2 ) steps, B took (n^2 ) steps, and C took (n^2 ) steps. For each algorithm write down all the possible formulas that could be associated with it.
(a) 7n · log_2 (n) + 12*log_2( log_2 (n))
(b) 7 *(22 log_2 n ) + n/2 + 7
(c) (2log4 n )/3 + 120n + 7
(d) (log2 n) 2 + 75
(e) 7n!
Explanation / Answer
Hi,
The pattern given is an exponential geomoetric 1,2,4,...
the sum of the series is given by
S= a. (1-r^n)/(1-r) where a is first term, r is common difference which is 2,/
so S= 2^n-1
so if given we want 2,147,483,647= 2^n-1
therefore n=31, after 31 days, we will have that number of points
Its the max value of int 32, therefore we need 32 bits to represent this
Now, losing is exactly the same pattern as this, N,N/2,N/4..
so if we can gain that number in 31 days, we can lose the same in 31
in general for N its given by above formula
2^t=(N+1), t is the number of days
c. Lets understand the notataion difference,
O() gives worst case complexity of given function/algorithm.
() gives best case complexity of given function/algorithm.
() gives average case complexity of given function/algorithm
here given O(n^2), (n^2),(n^2).
there can be infinitely many possible formulas associated with them
for ex A can be- 7n^2+ 8 or any Cn^2+ k
Similar case with the other 2, because all that we know from the notation is the worst, best and average case times
The options below 'c' i dont understand, should we solve something from them?
Thumbs up if this was helpful, otherwise let me know in comments. Good Day.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.