Talk:Analysis of algorithms

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, Top-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Top  This article has been rated as Top-importance on the project's importance scale.
 

Initial discussion[edit]

Why do you give the behaviour of binary sort as 1 + log2 N? Surely this is an implementation issue, and depends on exactly what you define as a step? Sjn28


Binary search, you mean. It does depend on what one defines as a step. Usually we want a step to be something which can be performed in time that is bounded above by a constant which depends only on the implementation. In this case each lookup at a particular position in the array counts as a step, and we assume that any such lookup can be done in a guaranteed amount of time. But if we were able to look at many entries in a single step, that would change the efficiency. Seb


Yes, I meant binary search. Sorry, slip of the brain. My point was that I don't think there's much point in saying any more than that the search is O(log N). Specifying something more specific like "3ceil(log_2(n)) + 2" or "2 log_2(n) - 1" is not terribly useful, because (a) you haven't defined what a step is; (b) it depends on exactly which datum you're looking for (you might be lucky); (c) other (unspecified) details of the implementation; but most importantly (d) it doesn't really matter what the constants are. Sjn28


I've updated the page. Tell me if you think it's better. Seb


Thanks! It's much clearer now. Sjn28

Outer loop[edit]

Is it correct that the outer loop executes (n + 1) times as in the statement 'The outer loop test in step 4 will execute ( n + 1 ) times'. I cannot see how this is the case as the loop appears to iterate from 1 to n, and if n were 1, the loop would execute only once. Bjwyse (talk) 16:57, 1 October 2008 (UTC)

Ok. Never mind. I see it includes the actual test for the loop condition so even if n were 0, the statement would execute once! Bjwyse (talk) 17:41, 1 October 2008 (UTC)

Footnote[edit]

What's the deal with the footnote "However, this is not the case with a quantum computer"? Aren't the commonly-understood models of quantum computers either non-deterministic Turing Machines (which are Turing Machines that (in deterministic time!) perform every possible state transition instead of just one state transition), parallel Von Neumann machines with an infinite number of processors, or black-box oracles that solve certain problems in constant time by magic? It doesn't seem familiar or meaningful to talk about some kind of computer that runs conventional algorithms, just not in deterministic time. 86.151.224.142 (talk) 09:02, 21 December 2008 (UTC)

removed sentence[edit]

I removed "Exact measures of efficiency are useful to the people who actually implement and use algorithms, because they are more precise and thus enable them to know how much time they can expect to spend in execution. To some people (e.g. game programmers), a hidden constant can make all the difference between success and failure." Of course implementers care about the exact time their program takes to run, but it would be hard to find any example where an exact complexity analysis is used as a tool. Almost all practical situations are much too complicated for that. McKay (talk) 00:14, 1 April 2009 (UTC)

Proposed merge of computation time[edit]

What's there to merge? A redirect seems more appropriate for now. The real beast of a WP:CFORK appears to be Algorithmic efficiency. Pcap ping 19:02, 22 August 2009 (UTC)

Right. I'll redirect. About Algorithmic efficiency: A beast indeed. A Balrog. --Robin (talk) 19:24, 22 August 2009 (UTC)
The last sentence in that article was not covered at computational complexity theory, and it should have been, so I copied it there. Pcap ping 20:17, 22 August 2009 (UTC)

What is [T1..T7].[edit]

This statement is unclear to me...

"A more elegant approach to analyzing this algorithm would be to declare that [T1..T7] are all equal to one unit of time greater than or equal to [T1..T7]."

Perhaps something more akin to the following is meant?...

A more elegant approach to analyzing this algorithm would be to declare each step executes in time k equal to one unit of time greater than or equal to Maximum of [T1..T7]. —Preceding unsigned comment added by 174.114.248.239 (talk) 22:05, 22 January 2011 (UTC)

I'll second this. What is trying to be said here? I'm not even sure that the comment above does much better. 69.66.249.35 (talk) 13:38, 13 April 2011 (UTC)

Why is this not the correct runtime for the for-loops[edit]

Outer will run n times. For each loop the inner will run 1,2,3,4...n times.

This means n*1 + n*2 + n*3 + n*4 times. Generally, n*(1+2+3+4+...+n) and we know the parentheses sum up to as Gauss said, sum of n numbers = n(n+1) / 2. Hence the running time is n*(n(n+1)/2 = n^3 + n^2 / 2 = O(n^3). — Preceding unsigned comment added by 129.11.106.156 (talkcontribs)

There is no outer multiplication by n; the outer loop's repetition has already been accounted for by virtue of the sum having 10 terms. The outer loop merely repeatedly adjusts the upper bound for the inner loop; it does not repeat each inner loop n times.
For it to be O(n3), the code would have to be:
for i = 1 to n
    for k = 1 to n # repeats n times
        for j = 1 to i # repeats i times
            print i * j
HTH, --Cybercobra (talk) 12:15, 8 March 2011 (UTC)

Ok thanks! Wouldn't be easier to argue in this way for O(n^2): The inner loop will run this many times, 1,2,3,...,n times. Which means 1+2+3+...+n = O(n) times.

Since it's wrapped in an outer loop that runs n times we get n * O(n) = O(n^2). —Preceding unsigned comment added by 129.11.249.250 (talk) 13:37, 8 March 2011 (UTC)

No, that's wrong. 1+2+3+...+n = (n*(n+1))/2 = (n2+n)/2 = O(n2), which is what the article already says. --Cybercobra (talk) 00:38, 9 March 2011 (UTC)

Maybe add[edit]

The discussion from Tarjan [1] on simplex vs. ellipsoid method asymptotic vs practical performance, which is a relevant example of this issue. Tijfo098 (talk) 16:54, 18 April 2011 (UTC)

What does "reasonable" in the preface part mean?[edit]

 However the efficiencies of any two "reasonable" implementations of a given algorithm are related by a constant multiplicative factor called a hidden constant.

This word's usage is confusing to non-professionals. Darth Ming (talk) 15:50, 1 May 2013 (UTC)

It is confusing to non-professionals and meaningless to professionals :-). Yet there is some purpose to the sentence. Consider for example an algorithm which is implemented by a good programmer in two different programming languages. The two programs won't run at exactly the same speed, but we can expect the speeds to be related (say, one of them is between 2 and 5 times as fast as the other for large problems). On the other hand, the programmer could add a lot of junk statements to the program to make it artificially run much slower — that would an example of an "unreasonable" implementation. McKay (talk) 07:52, 2 May 2013 (UTC)
I understand for professionals that word means nothing, but this is Wikipedia... I was just wondering how I can translate the sentence in Chinese without making it too lengthy. Thank you for the clarification anyway. :) Darth Ming (talk) 19:26, 2 May 2013 (UTC)