1
$\begingroup$

Nowadays we are interested to find some algorithms with a prescribed running time. For example if for certain decisional problem $X$ there is an algorithm with running time $O(n^3)$ we try to break down this value. Generally in literature the algorithms are presented as pseudocodes and then follows an informal analysis of this code that terminates with the phrase "the running time is $O(f(n))$".

I'm able calculate a time complexity only for a Turing machine, and in general the time complexity depends heavily on the model of calculus we are using. In fact the extended Church-Turing thesis only ensures a polynomial loss of time in changing our model. Practically my question is the following:

Question: Given a pseudocode, how is calculated the time complexity of the algorithm? To be more precise what are the elementary operations that define "one computational step"? For example, for a Turing machine this is clear since a computational step corresponds to applying the transition function.

Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ This is an incredibly subjective question. There are lots of different definitions. One of the main distinctions is whether arithmetic is considered O(1) or not. Another significant distinction is whether memory access is considered O(1) or not. "Given a pseudocode, how is calculated the time complexity of the algorithm?" that's not an appropriate question for a question/answer forum. You need to find some lectures and lessons, a better question would be "Are there any good online lectures teaching how to compute time complexity?" $\endgroup$ – DanielV May 30 '14 at 7:25
  • $\begingroup$ I'm reading texts like Sipser, Arora-Barak and Papadimitriou, but practically they deal only with Turing machines. But for example if you search on wikipedia some specific algorithm, there is the sentence "this algorithm runs in $O(f(n))$ steps"! How is calculated formally this time? I don't understand this. However I'm sorry if my question is not adequate. $\endgroup$ – Dubious May 30 '14 at 7:34
  • $\begingroup$ The methods are described in Knuth vol. I (or II?), of course, admittedly sometimes with a look at the concrete implementation (in MIX), but the general method for flow diagram is introduced. $\endgroup$ – Hagen von Eitzen May 30 '14 at 9:29
  • 1
    $\begingroup$ @fair-cointossing Well, to let you in on a secret, it's not well defined. I'll offer some of my own opinion. Turning Machines are completely useless machine models to calculate run time on. Their memory access doesn't reflect reality at all. Don't try to "formally" prove runtime. It's nearly impossible. You'd need a computer based proof assistant to actually formally prove the runtime of anything nontrivial. Assume memory access and small number arithmetic is constant time. These assumption are wrong, but everyone makes them and it keeps you sane. $\endgroup$ – DanielV May 30 '14 at 11:11
  • $\begingroup$ @DanieV Your comment comfort me a lot. I was going crazy on this fact. $\endgroup$ – Dubious May 30 '14 at 12:12

Your Answer

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

Browse other questions tagged or ask your own question.