Talk:Amortized analysis

Untitled

This page looks very much like the textbook sited below. So much indeed that it looks like copyright infringement. Perhaps that someone with knowledge about this subject could rewrite this page. Sadly I'm just learning about it so I don't have enough knowledge to say something about it. --Soyweiser 10:54, 17 November 2006 (UTC)

The statement "guarantees worst case performance" is confusing. It sounds like "guarantees that the algorithm will always perform in the worst way possible." This is especially a problem because the phrase is in the intro to the article. The phrase should be replaced with "guarantees at least worst case performance" or "defines the performance for the worst case" or " guarantees performance will be no worse than some lower bound" or something. — Preceding unsigned comment added by 216.243.5.110 (talk) 16:04, 3 August 2011 (UTC)

The term "worst case input" is used. If you can tell me what that means... For some size of input, this kind of input will produce the most number of steps? The problem is that for each size of input, the "kind" of input could be wildly different. — Preceding unsigned comment added by 68.147.63.98 (talk) 20:19, 18 March 2012 (UTC)

Copyright violation

Soyweiser is correct, there was/is copyright violation on this page. When whole ideas are taken from a published work, or very substantial text, slight reordering or adding other sources does not remove the copyright burden.

Example section was almost cut-and-pasted from Design and analysis of algorithms by V.V. Muniswamy. That's copyright infringement, so deleted. http://books.google.com/books?id=6eIPgTo8AaIC&pg=PA29&lpg=PA29&dq=%22In+average-case+analysis,+we+are+averaging+over+all+possible+inputs%22&source=bl&ots=shGN9VhF-X&sig=6voFhtpL8A8kzYV-GewTOZKRFVk&hl=en&sa=X&ei=-1YMULOyDeme2AW_2uHyDw&ved=0CDcQ6AEwAQ#v=onepage&q=%22In%20average-case%20analysis%2C%20we%20are%20averaging%20over%20all%20possible%20inputs%22&f=false 76.102.1.193 (talk) 19:53, 22 July 2012 (UTC)

Sigh. I note in the reviews for that book ... "V V Muniwamy is very good copy Master. He will just copy form differnet books and inform that he write the book. He is number one useless person. He cheated number of students in S V University, TPT". Whereever it ultimately came from, it's copyright violation. 76.102.1.193 (talk) 19:56, 22 July 2012 (UTC)

The fact that you were able to reproduce the entire work from Google Books: Fair use or copyright violation?--2001:18E8:3:104E:197F:49DD:AB15:A7EE (talk) 00:36, 18 February 2013 (UTC)

Possibly the rest of the page is copyright violation too. 76.102.1.193 (talk) 19:53, 22 July 2012 (UTC)

History

what is ment with probabilistic methods? i thought it's used to show existance, not runtime bounds? --141.53.220.223 (talk) 19:47, 11 July 2013 (UTC)

hyperlink on union linked to union(a type of datastructure). it should be linked to a document which infers about union operation. --Choi101104 (talk) 16:08, 11 July 2016 (UTC)

Confusing

Amortized cost is performed in 3 ways. aggregate analysis, counting analysis and potential method. — Preceding unsigned comment added by 111.68.105.84 (talk) 16:16, 15 May 2015 (UTC)

The first few phrases fail to explain the subject. — Preceding unsigned comment added by Jangirke (talk • contribs) 02:13, 28 January 2014 (UTC)

Is it possible to link to a resource that would explain what it means to divide O(n) by an integer -- otherwise it is not clear to the lay reader why the formula given to explain amortization holds. — Preceding unsigned comment added by 216.80.4.142 (talk) 15:15, 14 June 2018 (UTC)

Dynamic array example sounds wrong

The paragraph states :

In general if we consider an arbitrary number of pushes n + 1 to an array of size n, we notice that push operations take constant time except for the last one which takes O(n) time to perform the size doubling operation. Since there were n + 1 operations total we can take the average of this and find that pushing elements onto the dynamic array takes: O(n)/n+1=O(1), constant time

That explanation sounds wrong. For n operations, the doubling operations does not occur once, but lg(n) times, and each time cost lg(n) ops to do. Then, amortized, it will be lg(n)²/n, which boils down to O(1). — Preceding unsigned comment added by 217.114.201.77 (talk) 10:03, 24 August 2017 (UTC)

Dynamic Array Picture doesn't match the text

Perhaps this isn't a requirement, but the graph appears to be showing the cost of a dynamic array of initial length 0, rather than 4. MoeDrippins (talk) 14:56, 11 October 2020 (UTC)

Ruby to Python

Can someone rewrite the Ruby example in Python instead? Ruby is not popular and hard to understand. Python is much more popular and easier to understand and more familiar to readers. Frap (talk) 20:36, 6 February 2023 (UTC)