I'm learning about data structures and have been reading up on upper bounds. Most of the stuff I understand but my professor gave us a problem in class to solve on our own for fun. I'm not sure how to find the $O$ notation as a function of $N$ for this one.

for (i=1; i<=N; i++)
   for (j=1; j<=N; j+=i)

Also, does j+=1 make things different?

  • 1
    $\begingroup$ An extremely good compiler may be able to optimise this to $O(1)$ operations... $\endgroup$ – Pseudonym Sep 18 '17 at 1:45
  • 1
    $\begingroup$ Measuring bit complexity, I'm correct. The number of addition operations required to complete this algorithm is exactly one, because only the last iteration contributes to the final value of x. All of the other additions are dead code, and some modern compilers can spot this. $\endgroup$ – Pseudonym Sep 18 '17 at 3:18
  • 1
    $\begingroup$ @Pseudonym The question is whether we want algorithm cost or problem complexity here. Usually, people mean the former even though they say "complexity". Then, it's a question of the model: is code optimization considered or not? Usually, it's not. $\endgroup$ – Raphael Sep 18 '17 at 5:17
  • 1
    $\begingroup$ General note: it is perfectly feasible to analyse "useless" or deliberately inefficient algorithms. Such tasks may be deliberately assigned for didactic reasons. So saying, "this algorithm is useless so we don't need to analyse" or similar is misleading. $\endgroup$ – Raphael Sep 18 '17 at 10:11
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Raphael Sep 18 '17 at 10:41

You have one cycle in another cycle. In general that can be represented as

$$\sum_{i=1}^n\Big(f(n)+\sum_{j(i)} g(k)\Big)$$

Since former cycle contains nothing except another cycle, $f(n)\equiv0$.

So, you need to calculate $h_i(n)\equiv\sum_{j(i)} g(n)$ for every $i$. I have replaced $k$ with $n$ since it depends only on $n$. To do it try to understand how many iterations inner cycle will have.

If you are not successful, here is a hint:

$h_1(n)\equiv n,~h_2(n)\equiv n/2,~h_3(n)\equiv n/3...$

Once you will find an exact runtime, you want to convert it to big O. Googling that gave me an answer quick. Hope it helps.

Don't open following spoiler if you haven't understood what the function is

Converting to big O.


Not the answer you're looking for? Browse other questions tagged or ask your own question.