time complexity of a loop with conditions in it !!

time
time-complexity

#1

hi all…im using a nested loop in which i go into second loop if and only if it pass through a condition else do nothing…similarly the same in d second loop…if i run my both loops from i=1 to i=n what would be d time complexity ??


#2

Depends. It can be anything from O(NLog(LogN)) to O({N}^{2}). It depends on condition and value of increment. Sieve of erastothenes is nested loop, but it runs in O(NLog(LogN)) (due to increasing increment after every iteration+Decreasing chances of condition being true).

But on the other hand, any thing like “If number is even then run from i=1 to N, incrementing i by 1” will be clearly O({N}^{2}).