I have read the answer found here which considers the size of integers when doing comparisons and how that affects on the basic cost of comparison.
I am trying to understand why each basic operation takes $O(1)$ time. For example branches in general are considered to run in $O(1)$ time when they usually don't.
In computer architecture branches are considered the most time-consuming and problematic part of the code and this is one of the reasons why a loop is unrolled by the compiler in order to reduce the amount of branches the processor needs to execute.
For example a simple branch (let's say if a>b
) needs to do at least four things
- Get
a
from memory (whether it is cache or RAM or on disk does not matter; cache misses and hits are a different field of study). - Get
b
from memory - Evaluate the two and select the proper answer
- Search in instruction memory a new value for the Program Counter depending on the result of the evaluation.
Now get the variables from RAM is something done everywhere. So let's not count that.
But since all modern processors load more than just one instruction from instruction memory (let's say for our case 100) so as to reduce instruction memory accesses and a branch usually leads to a different place in the instructions list (let's say if a>b
call a method that swaps them), that would mean that branches take a lot more time than any other basic function.
Also in all modern processors multiplications and divisions take significantly much more time than additions and subtractions. Which is the reason why when multiplying or diving by numbers that are powers of two we should use logical bit shifting.
I know that in CS Theory and evaluating an algorithm we do not care. But in practice when implementing an algorithm the operations we use really effect the efficiency and complexity of our code.
So let's say we have three algorithms
- $n$ additions
- $n$ multiplications
- $n$ branches
In Theory all three of these compute in time $n$ but in practice, 1 is faster than 2, which is faster than 3.