Time complexity of enumerator

Question

enum class COLOR
{
    Blue,
    Red,
    Green,
    Purple,
    First=Blue,
    Last=Purple
};

COLOR operator++( COLOR& x ) { return x = (COLOR)(((int)(x) + 1)); }

COLOR operator*(COLOR c) {return c;}

COLOR begin(COLOR r) {return COLOR::First;}
// end iterator needs to return one past the end!
COLOR end(COLOR r)   {return COLOR(int(COLOR::Last) + 1);}


int main()
{
    for (const auto& color : COLOR()) std::cout << int(color); //0123
    return 0;
}

I have taken this piece of code from SO link.

I was asked time complexity of similar piece of code. As per my understanding, it is O(n) as all enumerator element are being iterated.
But right answer on some platforms says O(1) without any explanation.
Can someone confirm, is it O(1) and why?

Where does it say O(1)? What does "on some platforms" mean? – meowgoesthedog Aug 21 '17 at 10:56 — meowgoesthedog, Aug 21 '17 at 10:56

StoryTeller - Unslander Monica · Answer 1 · 2017-08-21T11:16:47.977

3

When you preform asymptotic complexity analysis, it's always important to define what your input size is. Because that's what the complexity is defined in terms of. Only then is the analysis meaningful in any way.

If for instance this algorithm is defined to have no input, then we can argue that the number of enumerators is fixed and is Last - First. As such the loop body will be executed a fixed amount of times, and is O(1) for it.

I can only guess that the "some platform" part may refer to the ability of compilers to optimize. When a compiler sees a loop that will be preformed exactly 4 times, it may very well choose to unroll it, instead of emitting code for an actual loop.

Having said that, optimizations don't really affect the asymptotic complexity of algorithms. They may at most affect the coefficient hidden behind the big-Oh notation. The loop is O(1) either way, according to the analysis we did above, but the coefficient is smaller after the unrolling optimization, since the code that pertains to looping is possibly gone.

edited Aug 21 '17 at 11:16

answered Aug 21 '17 at 11:05

StoryTeller - Unslander Monica

165,132
21
377
458

1

It should also be mentioned that loop unrolling doesn't effect asymptotic complexity. – Dan Aug 21 '17 at 11:13
1

@Dan - tried to give a more general explanation. What do you think? – StoryTeller - Unslander Monica Aug 21 '17 at 11:17
Does it mean that if I have a pre-filled data structure and iterate over it then its complexity will be called O(1). For same data structure if inputs are taken at run-time, then its complexity will be called something else? – Nipun Aug 21 '17 at 11:18
@Nipun - Like I said, it depends on how the input size is defined for the algorithm. An algorithms that is O(n) in general could be "collapsed" to O(1) if the input it receives is a pre-determined and immutable. If you look at the documentation of the standard library algorithms, they always define complexity in terms of the iterator pair they are passed. – StoryTeller - Unslander Monica Aug 21 '17 at 11:20
@Nipun: For all intents and purposes, you should consider it to still be O(n). Often we are truly limited by resources, such as the largest possible signed integer, or the amount of memory on a system, and therefore everything is "fixed", however Big-O notation is still useful for describing the relative performance of operations "as-if" the input size would grow toward infinity. – AndyG Aug 21 '17 at 11:50

Time complexity of enumerator

1 Answers1