CODEWITHSUNDEEP
javabig-o
user4262590
user4262590

Reputation:

Can someone explain to me about the right steps to get this answer for this java code, BigO/running time?

sum = 0;
 for(i=0;i<sqrt(n)/2;i++)
sum++;
 for(j=0;j<sqrt(n)/4;j++)
sum++;
for(k=0; k<8+j; k++)
 sum++;

The question is asking if it takes 10ms to run program for n = 100, how large a problem can be solved in 40 ms. The answer is 1600. My question is how did they get to 1600, I tried to plug it in N but I keep getting 200 instead?. Do I plug for the first N loop or the second N loop?

Upvotes: 0

Views: 307

Answers (3)

Sam Dufel
Sam Dufel

Reputation: 17608

All the runtime related to n deals with the square root of n.

We know that the run time scales proportionately to the square root of n, so we can say that the ratio of the square root of 100 to the runtime of 10ms will be equal to the ratio of the square root of x to the run time of 40ms, where x is the value of n which can be completed in 40 ms

Symbolically, that looks like this:

sqrt(100) / 10 = sqrt(x) / 40

A little algebra, and you get the value of n which will run in 40 seconds:

10 / 10 = sqrt(x) / 40

1 = sqrt(x) / 40

sqrt(x) = 40

x = 40^2

Upvotes: 0

echen
echen

Reputation: 75

The for loop with i is about the same runtime as the for loop with j and k. This is because j loops from 0 to sqrt(n)/4 where as k loops from 0 to 8+j which is close enough to looping from 0 to j. So the loops j and k iterate sqrt(n)/4 * 2 times which is just sqrt(n)/2 which is the same amount of iterations as the loop containing i.

Essentially you can boil it down to 

for (i=0; i < sqrt(n); i++)

after doing this simplification and then you can just plug in for n.

Upvotes: 1

Sinkingpoint
Sinkingpoint

Reputation: 7634

Consider the number of times the loops run. The first goes for sqrt(n) / 2 iterations, the second sqrt(n) / 4 and the last for 8 + j where j is some value (constant in the loop). Thus, for this entire code we have a complexity of sqrt(n) / 2 + sqrt(n) / 4 + 8 + j. In order to get the Big O notation, we take the fastest increasing one of these, ignoring constants i.e. sqrt(n). This gives us that the code runs in sqrt(n) time for a large n. Now we simply have to find an n such that sqrt(n) = 40 which is simply 40^2 = 1600.

Note also that this question is a bit silly, considering that Big O notation deals with only comparisons with large values of n (as we disregard constants and most terms). As such to do any form of computation like this with them is very odd indeed.

Upvotes: 1

Related Questions