1
$\begingroup$

lets say a data structure has operations called insert and delete both of which take O(log(n)) worst case. Suppose the amortized cost of insert is O(log(n)) and the amortized cost of delete is O(1).

Now if a sequence that has n delete operations performed on this data structure that has n elements currently, then what is the worst case? If delete takes O(1) amortized cost does this mean the worst case (not amortized) is O(n) for n delete's ?

I think no because it doesn't seem right but I'm not sure how to explain it

|cite|improve this question
$\endgroup$
  • $\begingroup$ Amortization usually refers to the entire sequence of operations on a data structure, not just some of them. $\endgroup$ – Yuval Filmus Mar 23 '19 at 8:12
  • $\begingroup$ I think you are right. Amortized cost is measured over unspecified-long sequence of operations, but since you can't delete more than N elements from this sequence, average cost of each operation in this procedure should be O(1) and therefore entire procedure is O(N). In other words, if this procedure require more than O(N) time, how one can say that amortized deletion operation cost is O(1)? $\endgroup$ – Bulat Mar 23 '19 at 8:53
  • $\begingroup$ sorry, I mean that answer to the question is yes, and therefore you are wrong $\endgroup$ – Bulat Mar 23 '19 at 9:05
1
$\begingroup$

The answer hinges on the definition of amortized cost. Since you haven't given such a definition, let me assume that you are using the common definition.

Consider a data structure supporting operations $O_1,\ldots,O_m$. These operations have amortized cost $T_i$ (where $T_i$ could depend on parameters) if the total cost of a sequence of operations run immediately after initializing the data structure consisting of $c_i$ many operations of type $O_i$ is at most $$ c_1 O_1 + \cdots + c_m O_m. $$ This bound only works if we consider all operations done on the data structure since initialization.

In your case, you are only considering one part of the operations performed on the data structure, and so amortized cost doesn't apply.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Yeah that would be the definition. So this wont be O(n) times for n delete operations because of the initialization cost ? Like my assumption of it being wrong was correct? $\endgroup$ – Tinler Mar 23 '19 at 18:48
  • $\begingroup$ The answer is, we don’t know either way from the given data. $\endgroup$ – Yuval Filmus Mar 23 '19 at 19:24
  • $\begingroup$ From cs.cornell.edu/courses/cs3110/2013sp/lectures/lec21-amortized/… I see that amortized cost is measured over n operations starting from arbitrary initial state $\endgroup$ – Bulat Mar 24 '19 at 6:08
  • $\begingroup$ @Bulat This is meaningless. Taking $n=1$, we recover worst case complexity. $\endgroup$ – Yuval Filmus Mar 24 '19 at 6:10
  • $\begingroup$ When n=1, any time is O(1). We can talk about some O(f(n)) only when we have some constraints for arbitrary n. Moreover, if we always start from empty structure, we can't say about amortized time of deletion per se. But googling for "amortized deletion time" brings a lot of results, including f.e cs.tau.ac.il/~orzamir/pub/FindMin_OrZamir.pdf $\endgroup$ – Bulat Mar 24 '19 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.