3

Recently I've read things about abstract machine and as-if rule (What exactly is the "as-if" rule?), and the requirements on time complexity of standard library (like this one: Is list::size() really O(n)?).

  1. Are the time/space complexity requirements on standard library in terms of abstract machine or in terms of real concrete machine?

If these are in terms of abstract machine, it seems an implementation can actually generate less efficient code in terms of complexity even though it seems not to be practical.

  1. Did the standards mention anything about time/space complexity for non-standard-library code?

e.g. I may write a custom sorting code and expect O(n log n) time, but if an implementation just treats this as code in abstract machine, it is allowed to generate a slower sorting in assembly and machine code, like changing it to O(n^2) sort, even though it unlikely will do that in real situation.

Or maybe I missed something about the transformation requirements between abstract machine and real concrete machine. Can you help me to clarify? :)

Even thought I mainly read things about C++ standard, I also want to know the situation about C standard. So this question tags both.

Willy
  • 581
  • 2
  • 10
  • 7
    "*Is the time/space complexity requirements on standard library are in terms of abstract machine or in terms of real concrete machine?*" I'm not sure how there would be a difference. Complexity doesn't change based on the machine. "*non-standard-library code*" How can the standard dictate anything about the complexity of non-standard library code? Complexity is a function of the *algorithm*, not of the binary. – Nicol Bolas Jun 24 '19 at 01:51
  • Thank you for explanation. I just want to know if it's possible or allowed. e.g. Maybe the single memory location access is not constant time, like some strange concrete machine (if there's any or any in past or future) that use tape as its memory. – Willy Jun 24 '19 at 02:17
  • 1
    "*Maybe the single memory location access is not constant time*" ... are you sure you know how algorithmic complexity theory works? Because "constant time" does not literally mean a fixed amount of time. It only means that the time does not vary relative to the N being measured. – Nicol Bolas Jun 24 '19 at 02:52
  • 1
    Got it. I think constant time means O(1) time. But for tape, a read/write time depends on current position and new required position, and it's Θ(M) where M is the distance between current position and new required position. If the input size N is larger, it likely the M will be also larger. So the Θ(M) can become Θ(N) for some steps in some algorithms, which is slower than O(1). Forgive and correct me if I misunderstood anything. :) – Willy Jun 24 '19 at 03:26
  • 1
    It doesn't matter how long it takes to execute one step in the algorithm. The big-O notation indicates the complexity of the steps _in the algorithm_. That won't change just because the data source changes from RAM to hard disk (or tape). For instance, the time complexity for the copy constructor of a std::vector is always linear, even if the stored elements are vectors (`std::vector>`) that also have linear complexity. – 1201ProgramAlarm Jun 24 '19 at 03:40
  • 1
    The C standard does not specify any time or space complexity. The `bsearch` can be implemented as linear search, and `qsort` with bogosort. – Antti Haapala -- Слава Україні Jun 24 '19 at 05:07
  • @1201ProgramAlarm Thank you for explanation. :) "The big-O notation indicates the complexity of the steps _in the algorithm_." Is this general for any time complexity notation or just for the standard? Because previously I would think if an algorithm runs in e.g. O(n) time, it usually means literally the running time, that is probably equivalent to # of steps, comparisons, etc., but sometimes it differs. It's appreciated if you can also give authoritative source on this so that I can fully clarify it. – Willy Jun 24 '19 at 05:49
  • @Willy It's always in terms of "lower" operations, e.g. comparisons and swaps for search and sort. It's usually clear from context what `n` is, if it is unstated. – Caleth Jun 24 '19 at 12:20

3 Answers3

1
  1. Are the time/space complexity requirements on standard library in terms of abstract machine or in terms of real concrete machine?

The complexity requirements are in terms of the abstract machine:

[intro.abstract] The semantic descriptions in this document define a parameterized nondeterministic abstract machine...

  1. Did the standards mention anything about time/space complexity for non-standard-library code?

No. The only complexity requirements in the standard are for standard containers and algorithms.

if an implementation just treats this as code in abstract machine, it is allowed to generate a slower sorting in assembly and machine code, like changing it to O(n^2) sort

That's not the worst thing it can do. An implementation can put the CPU to sleep for a year between every instruction. As long as you're patient enough, the program would have same observable behaviour as the abstract machine, so it would be conforming.

eerorika
  • 232,697
  • 12
  • 197
  • 326
0

Many of the complexity requirements in the C++ standard are in terms of specific counts of particular operations. These do constrain the implementation.

E.g. std::find_if

At most last - first applications of the predicate.

This is more specific than "O(N), where N = std::distance(first, last)", as it specifies a constant factor of 1.

And there are others that have Big-O bounds, defining what operation(s) are counted

E.g. std::sort

O(N·log(N)), where N = std::distance(first, last) comparisons.

What this doesn't constrain includes how slow a comparison is, nor how many swaps occur. If your model of computation has fast comparison and slow swapping, you don't get a very useful analysis.

Caleth
  • 52,200
  • 2
  • 44
  • 75
-1

As you've been told in comments, the standards don't have any requirements regarding time or space complexity. And addressing your additional implicit question, yes, a compiler can change your O(n log n) code to run in O(n²) time. Or in O(n!) if it wants to.

The underlying explanation is that the standard defines correct programs, and a program is correct regardless of how long it takes to execute or how much memory it uses. These details are left to the implementation.

Specific implementations can compile your code in whichever way achieves correct behavior. It would be completely permissible, for instance, for an implementation to add a five-second delay between every line of code you wrote — the program is still correct. It would also be permissible for the compiler to figure out a better way of doing what you wrote and rewriting your entire program, as long as the observable behavior is the same.

However, the fact that an implementation is compliant doesn't mean it is perfect. Adding five-second delays wouldn't affect the implementation's compliance, but nobody would want to use that implementation. Compilers don't do these things because they are ultimately tools, and as such, their writers expect them to be useful to those who use them, and making your code intentionally worse is not useful.

TL;DR: bad performance (time complexity, memory complexity, etc.) doesn't affect compliance, but it will make you look for a new compiler.

aaaaaa123456789
  • 5,541
  • 1
  • 20
  • 33