educative.io

Example 1 : Measuring Time Complexity


#1

I have a problem with this example, never learned this topic before, so im a total newbie at this.
Time complexity = 1 + n + (1 + 1 + 1 + … + 1) + n + 1⇒= 1 + n + n + n + 1⇒3n+2

3n + 2, ok… so i was looking into this and i might understand why this is 3n instead of 2n, and this should be the reason (1 + 1 + 1 + … + 1) becomes one of the 3n, right?

Im starting the course Big-O Notation For Coding Interviews and Beyond, this one will probably clear things up for me


#2

Hi Matias,

Yes. You’re right about this as you have understood it well.

1 + n + (1 + 1 + 1 + … + 1) + n + 1

(1 + 1 + 1 + … + 1) this whole thing computes to n as this runs n times

1 + n + n + n + 1

2 + 3n

So, yes you got the right reason.

Regards
Team Educative.