CODEWITHSUNDEEP
schemeracket
Masterminder
Masterminder

Reputation: 1135

Runtime of set! and begin in Scheme/Racket

Does anyone know what the runtime of set! and begin is in Scheme/Racket?

I think set! is constant but I'm not sure.

Upvotes: 1

Views: 310

Answers (4)

Greg Hendershott
Greg Hendershott

Reputation: 16260

If you're concerned about the performance of set!, keep in mind that avoiding mutation can be faster. See Racket Guide: Mutation and Performance.

Upvotes: 1

Óscar López
Óscar López

Reputation: 236004

The set! operation simply associates ("binds") a value to a symbol, surely that's O(1) in any self-respecting programming language. Looking for a binding might not necessarily be O(1) depending on implementation details, but that's an entirely different matter (I don't know the specifics for Racket).

Regarding begin, that's a sequencing form, applying it doesn't have a cost per-se, only its contents (the expressions it holds inside) will determine its time complexity. Same thing for set!, the value part of the assignment might take some time to evaluate, but the set! operation itself is O(1)

Upvotes: 2

John Clements
John Clements

Reputation: 17203

One caveat: set! and begin both have subexpressions. If either of these takes a long time, then evaluation of the set! (or begin) will, as well.

Upvotes: 2

soegaard
soegaard

Reputation: 31147

set! is O(1). There is no difference in this regard between Scheme and other languages.

Upvotes: 2

Related Questions