CODEWITHSUNDEEP
algorithm
ptratyou
ptratyou

Reputation: 13

Running time for this algorithm

count=1
for (i=0;i<N;++i)
    for (j=0;j<i*i;++j)
        for (k=0;k<j;++k)
            ++count

For this algorithm how this is O(n^4): I saw a post that people answer it as O(n^4)

Isn't this close to O(n^5)?

if I take math equation yes, it becomes 1+....(n^2+n^2). it will be the sum of the sequence of (N^2+N^2) but that is also close to O(n^5) when I actually run the program.

for(int=i; i*i<=n; i++)
   for(k=1; k<=i; k++)

when I simply check -- I make it as first loop goes

sqrt(n) times

second loop goes

k <= i <= sqrt(n)

thus it becomes sqrt(n) times.

Overall, the iteration runs O(n) times without forming math equation. So if I use the same approach I get O(n^5) and is this correct approach - lets say you have to get it during the exam and they ask you asymptotic Big O running time.

Upvotes: 0

Views: 58

Answers (1)

User_67128
User_67128

Reputation: 1250

This is O(N^5),

for (i=0;i<N;++i)           O(N)
    for (j=0;j<i*i;++j)     O(N^2)
        for (k=0;k<j;++k)   O(N^2)

As a result it is O(N^5).

I have a answer for a similar question here, How does this if statement affect the time complexity?.

Upvotes: 1

Related Questions