-1
$\begingroup$

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)
       x=i+j;

Also, does j+=1 make things different?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ An extremely good compiler may be able to optimise this to $O(1)$ operations... $\endgroup$
    – Pseudonym ♦
    Sep 18, 2017 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, 2017 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, 2017 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, 2017 at 10:11
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – Raphael ♦
    Sep 18, 2017 at 10:41

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$

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