News
Exercise Sheet 7 Task 3.a
Written on 10.12.2024 10:20 by Niko Hastrich
Dear all,
we have noticed that the intended solution for subtask 3.a on exercise sheet 7 was not correct, and decided that every student should get full credits for this subtask.
The problem lies in the fact that n in this task refers to the number of elements currently present in the data structure. If we do not allow deletions, then we need at most (1 + log n)-many arrays to hold all elements. However, if we allow deletions (which were intended to just pop the last element of some list), this is no longer the case as there are sequences of operations such that afterward we have n lists with one element each. This breaks the running time of the intended solution. Rather, the running times should have referred to the number of insert operations N, that have already taken place.
We deeply apologize for any inconvenience that were caused by this error.
Best regards,
Niko