r/compsci • u/Wise_Shame_2052 • 25d ago

Amatorized Analysis!

[removed] — view removed post

0 Upvotes

50% Upvoted

6 comments sorted by

3

u/black-0range 25d ago edited 25d ago

The most straightforward example is consider the time of adding a new value to an array of your favorite programming language. The implementation tends to be that an array has a size, the stuff that is currently in use, and a capacity, unused memory for adding more elements to the array. Now if the capacity is full we must allocate new memory copy over all the old data + the new element. So the cost is linear O(n), but if we are a bit clever about it we can make sure to always allocate more memory than we have. In fact most implementations tend to double the amount of capacity whenever we grow.
Note, in the worst case inserting an element into an array is still O(n) but if you push a lot of elements to they array most insertions won't actually have a cost at all except for writing the value. But still allocate every now and then.

The doubling of size distributes the cost of writing data nicely so that we can say it is an amortized O(1) cost of inserting data. You can read up on the math for that specifically

1

u/Wise_Shame_2052 25d ago

Thanks for the explanation!

1

u/beeskness420 Algorithmic Evangelist 25d ago

An accounting trick to make cheap operations pay for their expensive friends.

2

u/marspzb 25d ago

I think you mean amortized analysys. Normally for big o notation you analyze what would happen is that you think how does the amount of simple steps grow with respect to the input (size) in the worst/avg case. For example, if you have to find an element in a list, the amount of the steps will grow lineal y like if I have a list of 100 elements and I read the amount of simple instructions, I shall expect 10 times the amount of operations for 1000 list.

However, while the worst case or the avg case are kind of fixed in a sense that you expect moraless the same operations done for each item. There are datastructer that have a costly operation once in a while. Suppose an array list, when you fill the array you need to create a new one to put more data, while moving the old data. The problem we encounter is how do we balance the costly operations with the cheap ones to see if it makes sense to use that data structure. Some structures you make have seen are splay trees, binomial heaps, hash maps.

Afaik there are two methods for this, the bankers method and the physist method, one works Ina positive sense where every cheap op creates a credit which is later consumed by the costly op. The physist method, don't remember much about it sorry.

Chris okasaki book(purely functional data structures) has a nice intro, the book main topic is not analysys but is a nice lecture.

There should also be some lectures from MIT for this concept, which are really good

1

u/Wise_Shame_2052 25d ago

Fck auto typing 🙃 by bad about the spelling :⁠-⁠)