Complexity and semantics

[Jean-Guillaume Pyraksos]

Say that you have computed a factorial function fac(n) with a given
complexity.
Let proj(x,y) := x and f(n) := proj(0,fac(n)).
What is the complexity of the function f ?

Most books use a pseudo-language without saying anything on the
semantics of its function call, as if algorithmics was completely
disconnected from programming. A pseudo-language is a programming
language.

JG

[Dan Doel]

Post by Jean-Guillaume Pyraksos
Say that you have computed a factorial function fac(n) with a given
complexity.
Let proj(x,y) := x and f(n) := proj(0,fac(n)).
What is the complexity of the function f ?
Most books use a pseudo-language without saying anything on the
semantics of its function call, as if algorithmics was completely
disconnected from programming. A pseudo-language is a programming
language.

The answer depends on the evaluation strategy of the language. If the
function calls are necessarily strict, then it's reasonably accurate to say
that the complexity of f is the same as that of fac. If the evaluation
strategy is non-strict, then f is presumably O(1) (because fac(n) has no
reason to be evaluated at all).

[Paul Rubin]

Post by Jean-Guillaume Pyraksos
Most books use a pseudo-language without saying anything on the
semantics of its function call, as if algorithmics was completely
disconnected from programming. A pseudo-language is a programming
language.

TAPL discusses three styles of programming semantics: denotational
semantics, axiomatic semantics, and operational semantics. Complexity
questions mostly fall under the operational semantics umbrella. I get
the impression that PL theory doesn't deal so much in operational
semantics a lot of the time, in part because we want compilers to be
able to optimize programs. So often the denotational semantics are
specified and the operations are left up to the implementation.

In your example, even in a strict language, once the specification of
the factorial function is known, a compiler might be able to optimize it
away by partial evaluation.