A subreddit for all questions related to programming in any language.
Hi, I have recently gotten into generators and I am confused regarding analysing its complexity
I was told that a code that looks something like this would be O(1)
def gen(self):
for some_value in self.array:
yield some_value
But what if I had a slightly modified function that looks like this
def gen(self):
for some_value in self.array:
if some_value is not None:
yield some_valueWould this still be O(1)? or would it be O(n)?
I would gladly take any advice on how to interpret these functions
Thank You!
Sort by:
Best
Open comment sort options
Best
Top
New
Controversial
Old
Q&A
Those are both O(N). If there are N elements in the array, both of those functions need to do N things.
When discussing time complexity, you have to be careful to define what you're talking about.
The first one is O(1) per iteration -- that is, per call to
next()on the generator. It takes O(n) time to exhaust the generator -- that is, to keep callingnext()until you get aStopIteration. Or equivalently, to iterate over it to completion with aforloop.The second one is O(n) per iteration, in the worst case. If you have an array containing n
Nonevalues, then the very first call tonext()will iterate through the entire array without ever yielding, taking O(n) time. On the other hand, if none of your array elements areNonethen it will be O(1) every time. If a fixed fraction f of your array elements contain non-Nonevalues, then the average time per iteration will be O(1/f), because on average each invocation of the generator will have to skip 1/f elements.But it is still O(n) in total, because no matter how many
Nonevalues are in the array, you won't need to do more than n iterations of theforloop that iterates through the array. And each of those iterations is constant time, including the time taken to yield and resume (which will happen at most once per iteration).An algorithm will take the same amount of time whether it's implemented using a generator or not. The use of a generator has zero impact on time complexity assuming the algorithm is identical between implementations.
What it does have an impact on is memory complexity. When generating large sequences, a naive solution using a loop will have to build the entire sequence in memory, whereas a generator only needs to hold 1 item in memory at a time.