1

I need to find the O-notation for the following bit of code:

for(i = 0; i < N; i++){
  for(j = 0; j < N; j+=i){
    x+=y;
  }
}

I've been able to get it down to O(N*log(N)), but I want to be sure.
Does this kind of function have a name I can look up and research?

m_man15
  • 19
  • 1

2 Answers2

6

Your code is O(∞). On the first outer loop, i is 0, which means your increment for j is 0, and therefore the inner loop becomes an infinite loop when N > 0.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
5

For the case when i starts from 0:

Your code is O(∞) as explained by ShadowRanger's answer.

For the case when i starts from 1:

You can simply use the observation that your actual complexity f(N) is bounded by:

f(N) <= N/1 + N/2 + N/3 + ... + N/N 

     <= N * (Bound of value of Harmonic Number) 

     < c1 * N * ( log (N) ) i.e. O( N log(N) )

To prove that value of Harmonic number is O( log(N) ), you can use simple calculus. Refer here and here.

รยקคгรђשค
  • 1,919
  • 1
  • 10
  • 18