Talk:Analysis of algorithms
|WikiProject Computer science||(Rated C-class, Top-importance)|
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
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)
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. 220.127.116.11 (talk) 09:02, 21 December 2008 (UTC)
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
- Right. I'll redirect. About Algorithmic efficiency: A beast indeed. A Balrog. --Robin (talk) 19:24, 22 August 2009 (UTC)
What is [T1..T7].
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 18.104.22.168 (talk) 22:05, 22 January 2011 (UTC)
Why is this not the correct runtime for the for-loops
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 22.214.171.124 (talk • contribs)
- 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
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.
- 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)
What does "reasonable" in the preface part mean?
However the efficiencies of any two "reasonable" implementations of a given algorithm are related by a constant multiplicative factor called a hidden constant.
- 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)