2
$\begingroup$

Edit: Since this post is gaining traction, I feel the need to clarify that the purpose of this is to see if asymptotic and constant factor estimations calculated from high level code implementations of algorithms are reasonable approximations of the true version. I am not trying to predict the speed of code when running.

Suppose I have some sequence of code $C$ in a high level language (C++, Python, Java, etc.) which needs to be converted into machine code which we will call $M$. Obviously machine code varies from system to system, so assume we are on a fixed machine

Under a uniform cost model, we can say that every instruction of $M$ costs $1$ operation, so we can calculate the complexity of our code as some function of the input size of our problem $n$. Let an upper bound of this function be $f_M(n)$.

Clearly, nobody writes in machine code, so we can approximate $f_M(n)$ by counting operations of our high level language code $C$, which we can say $f_C(n)$

Define $1$ operation of $C$ to be the following

1. Function Calls
2. Returning
3. Arithmetic Operators
4. Logical Operators
5. Comparisons
6. Pointer/Object dereferencing/Array indexing
7. Variable Assignment

This list is heuristic, and was given to me as a means of approximating by an engineer mentor, so if a better heuristic exists please let me know.

Questions: Given $f_C(n)$, are we guaranteed any of the following, assuming the code is compiled in "good faith" (no additional logic added to insert unnecessary operations)

  1. Does $f_C(n)\in \mathcal{O}(g(n))$ imply $f_M(n)\in \mathcal{O}(g(n))$?
  2. Does there exist a constant factor such that $f_M(n)\leq c\cdot f_C(n)$? for sufficiently large $n$?
Improve this question
$\endgroup$
1
  • $\begingroup$ The heuristic for C is typical for a language that compiles to machine code. But the examples of high level languages you give include Python and Java, which don't. Python for instance has to do name lookup at runtime, which is generally not an O(1) operation $\endgroup$
    – MSalters
    Commented Jul 4, 2023 at 12:14

6 Answers 6

Reset to default
6
$\begingroup$

Yes, this is reasonable as a first cut approximation. As always, there are caveats.

A theoretical model is a model. It is used for making predictions, but models typically are not perfect, and there are some factors that they don't take into account.

I'm not sure what you mean by function calls, but some functions might take a very long time to execute, so a single function call might take a very long time, unless you are also careful to count all of the operations that are done by the function you are calling. So I will assume that you are also counting the time to execute the body of every function that is called, otherwise there is a major flaw.

This does not take into account the effect of memory hierarchy. For instance, random access memory lookups might be noticeably slower than sequential memory access, because of cache effects. This is not taken into account by the model you articulate -- partly because it is very challenging to model.

If you are concerned with practical running times, there are no guarantees. A single memory access could cause a page fault (e.g., if there is thrashing due to memory pressure) and loading data from disk, which a long time, compared to executing a single instruction.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry yeah I should clarify that by Function Calls I meant the overhead to actually enter the function (adding to the stack trace etc.), the actual body is added as well. For caching, could we compute assuming worst case scenario with no caching at all? $\endgroup$
    – wjmccann
    Commented Jul 3, 2023 at 19:22
  • $\begingroup$ @wjmccann, you could, but because the worst case is so vastly much worse than the average case, it's not necessarily very predictive of actual performance. Sometimes an $O(n \log n)$ time algorithm with sequential memory access can be faster than a $O(n)$ time algorithm with random memory access. This is true whether you work with a high-level language or low-level code, though, so it might be orthogonal to what you are asking. $\endgroup$
    – D.W. ♦
    Commented Jul 3, 2023 at 22:43
2
$\begingroup$

The answer actually depends on the how many machine operations are utilized by an operation of the high-level language. If each operation of $C$ takes a constant machine operations, then the answer to your questions is yes.

However, you can design a high level language that implements a multiplication using addition. So multiplying two integers $2$ and $n$ with input size $\log(n)$ could actually take expoenential time $2^{\log n}$.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ More realistically, define an unbound integer type in C. Even addition will be O(N). Addition is O(1) in machine code only because the number of bits in a register is fixed. $\endgroup$
    – MSalters
    Commented Jul 4, 2023 at 12:08
2
$\begingroup$

The whole story of complexity evaluations is that you count the operations that execute in bounded time (they also say in $O(1)$). Whether you consider a high-level language or concrete machine language, the costs need not be unit nor even constant (independent of the values of the arguments), this does not matter: as long as you don't involve operations that themselves have a dependency on $n$, the asymptotic complexities in any model are equivalent.

Now when you translate from one language to another, a single operation in one model translates to a bounded number of operations in the other. E.g. a multiply & add opcode that translates to one multiply and one add, no more. So when computing the overall complexity, if you collect the terms with the dominant asymptotic complexity, you get $\le c_0f(n)$ in one case, and $\le c_1f(n)$ in the other. The relation between $c_0$ and $c_1$ depends on the respective times of the elementary operations and the ratio of their counts across the translation. And we just don't care about this relation.

In practice, it is overkill to accurately count every operation, such as giving a weight to call or return. What you do is to select a representative operation (such as a comparison or a data move) such that the number of other operations is of the same order.

E.g. if you look at bubble sort, every time you perform a comparison, you perform zero (no swap) or three moves (swap), and no other operation (loop control) is performed more often.

The answer to 1 is true. In principle 2 is false, because all we know is

$$f_M\le c_M\cdot g(n)\land f_C\le c_C\cdot g(n).$$

But in reality, the ratio of the constants cannot be as large as one wants and the following bracketing will hold:

$$c_0\cdot f_M(n)\le f_C(n)\le c_1\cdot f_M(n).$$

This reflects the fact that one operation corresponds to a bounded number in the translation.

Improve this answer
$\endgroup$
1
$\begingroup$

One kind of high-level operations that may not translate to constant-time machgine code are memory management operations, such as alloc/free or new/delete.

There are allocators with constant-time operations for constrained conditions (e.g. fixed block allocators, the stack), but for a general allocator some operation is nonconstant (search for a free block, update free block set/list/X on deletion, compaction, etc.).

Improve this answer
$\endgroup$
1
$\begingroup$

There is asymptotic behaviour, and there is real time measurements. Asymptotic behaviour tells you how the time that your algorithm takes will grow as your problem size grows, assuming operations take constant speed. Things like adding, subtracting, multiplying, dividing will take constant speed, if the operands have a fixed size. One trillion divisions will take a million times longer than a million divisions. On the other hand, I have a computer now with 8 cores running at about 3GHz each, and doing multiple operations per processor cycle. In 1984 I had a computer running at 8 MHz and taking multiple cycles for each operation. There is a huge speed difference, which isn't accounted for by asymptotic behaviour at all. So asymptotic behaviour isn't everything.

Now accessing memory is tricky, and your "constant factor" assumption falls apart. Some values are stored in registers and can be accessed super fast. Some values are in L1 cache and can be accessed very fast, then you have slower L2 cache, some machines have an even slower L3 cache, then comes slow RAM, then even slower memory that is handled by a different core, and then virtual memory which is an awful lot slower. And then you reach a limit where currently you cannot access more memory. Big-O assumes that your problem size can be large beyond any limit. And you can't have that on a real machine.

Improve this answer
$\endgroup$
0
$\begingroup$

I think that the whole approach is flawed. Modern compilers and computers are way to complex for that.

What you should do: Implement the code, measure the speed with good benchmarking software for a large variety of input values.

Analyse the result with statistics software. You will see if the runtime is linear, quadratic, exponential (or something else) in the data.

Improve this answer
$\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.