Skip to main content

New answers tagged

0 votes

When do we multiply or add the time complexities of loops?

There is no simple rule with O(f(n)). If loop 1 takes $\Theta(f(n))$ and loop 2 which is run once for every iteration of loop 1 takes $\Theta(g(n))$, then the total is $\Theta(f(n) \cdot g(n))$. The ...
gnasher729's user avatar
  • 30.6k
-2 votes
Accepted

When do we multiply or add the time complexities of loops?

Big-O is about worst-case, this means you can typically focus on a simplified version of the function you've got. For worst-case, you need the consider the case where the early returns is not taken, ...
Matthieu M.'s user avatar
2 votes

When do we multiply or add the time complexities of loops?

Here's the gist of it, but you should try to make it more formal on your own. Ignore, for now the "if bla bla, return True" part. Notice that essentially any time anything interesting ...
Pål GD's user avatar
  • 16.7k

Top 50 recent answers are included