CODEWITHSUNDEEP
time-complexitybig-o
Destiny Coots
Destiny Coots

Reputation: 27

Find Big O Running Time

I am having difficulty figuring out the big o notation running time of this piece of code. I would think it's O(n) because i=0 and the first while loop keeps going until i = n but then the second while loop comes in and the whole thing is throwing me off.

i=0
sum = 0;
    while i<n:
       sum++
       if i==3 or i==7 or i==5:
          j=0
          while j<n:
             sum++
             j++
       i++

Upvotes: 1

Views: 192

Answers (3)

abalcerek
abalcerek

Reputation: 1819

It indeed is O(n). If you had no if statements you would have O(n^2). But inner loop is running at most 3 times so it is equivalent to O(3n) and O(n).

Upvotes: 2

Trần Đ&#236;nh Huy
Trần Đ&#236;nh Huy

Reputation: 11

It's still O(n). The second while loop take 3n time in the worse case .( n>=8)

Upvotes: 1

chepner
chepner

Reputation: 531055

The inner loop only executes, at most, 3 times. For large values of n, the total time spent in that loop will be inconsequential to the overall running time.

Upvotes: 1

Related Questions