1
$\begingroup$

My algorithms textbook defines $T(n)$ as "the number of computer steps needed to compute fib1(n)" (where fib1(n) computes the $n$th Fibonacci number recursively). I am wondering what exactly "the number of computer steps" means- is it the number of lines executed by the program (often times "stepping through code" in the debugger means to go line by line in the debugger)- or is it something else, like the number of operations (add, multiplying, equality checks, etc.)?

In context, it is hard to tell, as both interpretations could explain values of $T(n)$. Below is the provided pseudocode for fib1(n) (the book merely says for $n \leq 1, T(n) \leq 2$)

function fib1(n)
if n=0: return 0
if n=1: return 1
return fib1(n-1) + fib1(n-2)

Perhaps the way the fact that the book used an inequality without precisely saying the value of $T(n)$ when $n \leq 1$ suggests there is no hard and fast rule on what constitutes a computer step; however, should I think of what a computer step is here?

$\endgroup$

2 Answers 2

3
$\begingroup$

In runtime analysis, we usually define something called a basic operation that can be executed in constant time under the assumed computation model. Since we are going to do an asymptotic analysis, the exact values of these constants for different operations aren't going to matter much. Thus, we can simply count the number of such basic operations (steps in your case) to simplify our complexity analysis.

In your case, it is better to write that $T(n) \le c = O(1)$ for $n\le 1$ and some positive constant $c$, since there can be multiple operations involved for a conditional block like if n == 0: return 0.

$\endgroup$
2
$\begingroup$

“Computer steps” has intentionally no precise definition. This is usually about execution time, and we assume that every computer has a constant time T, which is different for every computer, and each “computer step” can be performed in time T.

So if you calculate the execution time of an algorithm as O(f(n)) or $\Theta(f(n))$ etc, then the result applies to all kinds of different computers.

If you care about real execution time in seconds or nanoseconds on a particular computer, then you either measure, or you do a much more elaborate calculation of the execution time. The difference will only be a constant factor, but for example if a self driving car brakes after 100ms or 10 seconds when it spots an obstacle, that’s only a constant factor but makes a huge difference to your health and to your wealth.

(As an example: i wrote some code that i wanted really fast. Turns out my computer can start four floating point multiplication every cycle. Each takes 4 cycles to finish. So if you only count operations you can be off by a factor 16. But a times b plus c is also “one computer step” taking the same time, so in four cycles you can do 16 multiplications AND 16 additions. And vector operations with two double precision or four single precision operations are also one “computer step”, so the number of multiplications can be multiplied by another factor two or four).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.