CODEWITHSUNDEEP
pythonalgorithmdata-structuresbig-otime-complexity
Mayank Sharma
Mayank Sharma

Reputation: 123

Running time of the function below

The outer loop runs n times but i am unable to find the running time of inner loop and the total running time, can you please help regarding this?

def function(n)
    count=0
    if n<=0:
        return
    for i in range(1,n):
        j=1
        While j<n:
            j=j+i
            count = count+1
    print(count)

Upvotes: 1

Views: 55

Answers (1)

amit
amit

Reputation: 178451

The inner loop runs O(n/i) times, for each value of i.

If we sum it over all values of i we get:

n/1 + n/2 + n/3 + ... + n/n = n* (1 + 1/2 + ... + 1/n)

The sum 1 + 1/2 + ... + 1/n is the harmonic number, which is in O(logn), so your code is O(nlogn)

Upvotes: 1

Related Questions