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?
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