Can anyone explain the steps to calculate the time complexity of this code and what it would be?"

Question

I have a code snippet that I would like to analyze for time complexity. The code is as follows:

for (i=1; i<=n; i++) {     
    for (j=1; j<=n; j=j+i) {         
        printf("x");     
    } 
}

I would like to know the time complexity of this code

What do _you_ think the time complexity of this is? Is `n` a constant, or a user input? — Chris, Apr 13 '23 at 02:29
@EricPostpischil I believe Chris was trying to let OP think through the question again and try and get the solution. If n is fixed, ie 5, then the program will not be a function of n. Just thoughts though — Onyambu, Apr 13 '23 at 03:08
Minor stylistic suggestion as an aside: `j = j + i` == `j += i` — Chris, Apr 13 '23 at 06:54
Does this answer your question? [Finding Big O of the Harmonic Series](https://stackoverflow.com/questions/25905118/finding-big-o-of-the-harmonic-series) — nielsen, Apr 13 '23 at 07:49

score 2 · Answer 1 · answered Apr 13 '23 at 03:04

The complexity is proportional to the number of Xs you get, which is roughly:

n + n/2 + n/3 + n/4 ... n/n

That is

n ( 1 + 1/2 + 1/3 + 1/4 ... 1/n)

The second term is the harmonic series. It comes out to about log_e n, so your total complexity is O(n log n)

1 Answers1