educative.io

Educative

Example 1: Measuring Time Complexity Math Question

The equation shows: Time complexity = 1 + 1 + n + (1 + 1 + 1 + … + 1) + 2n + 1⇒
= 2 + n + n + 2n + 1⇒4n

Shouldn’t 2 + n + n + 2n +1=>4n + 3?

This is actually 1 + 1 + n + (1 + 1 + 1 + … + 1) + 3n + 2⇒
= 2 + n + n + 3n + 1⇒5n + 4.
This is because the print(sum) statement takes 2 operations, for variable access and display, respectively, and sum+=1 takes 3 operations, variable access, addition, and variable assignment.

Happy learning!
Anum Hassan|Developer Advocate
Educative.io