I'm trying to understand how to answer this question: Given an algorithm A (some algorithm, no idea what it actually does) with average time complexity O(log n) and worst case complexity O(n), prove/refute the following:
- There exists an algorithm B that executes the same program as A that has the time complexity O(log n) on average amortized.
- There exists an algorithm C that executes the same program as A that has the amortized time complexity O(n).
- There exists an algorithm D that executes the same program as A that has time complexity O(n^2) at worst.
It looks as if I supposed to prove it but I do not completely understand how am I supposed to do that mathematically, specially because I am not given the algorithm A and have no idea how it works. For B I am confused because how can it be both? Won't the fact that it is supposed to be on average the more dominant thing because we already know that on average A's complexity is O(log n)? So confused about this whole question...