-1

I am new to time complexities and asymptotic notation. I was looking at this video: https://www.youtube.com/watch?v=9TlHvipP5yA to figure out the time complexity of a piece of code shown below

The code concludes that the time complexity for the code below is O(Sqrt(n));

When I supply different n values, I am expecting Sqrt(n) # of outputs but this doesn't verify the O(Sqrt(n)) analysis. Can someone please explain why it is so?

For example if I have n = 10, I am expecting Sqrt(10) outputs which is ~ 3 outputs or 4 if you round up I guess. IS this illogical?

Thanks in advance. 

p = 0;
for( int i = 0; p <= n; i++){
  p = p + i;
  System.out.println(p);
}
Spindoctor
  • 434
  • 3
  • 17
  • Sorry for the mistake. I have fixed the code. – Spindoctor May 30 '19 at 18:47
  • I don't understand what you're asking. What exactly is your question? – melpomene May 30 '19 at 18:50
  • Big O describes the asymptotic behavior (up to multiplication by a constant) for large values of n. You can't deduce what the time for n=10 will be from it. – interjay May 30 '19 at 18:51
  • OK so it is wrong to assume that if I have n = 100, I will have root(100) System.out.print statements? – Spindoctor May 30 '19 at 18:53
  • No. If 100 is large enough to exhibit the asymptotic behavior then you'll get up to c*sqrt(100) prints for some constant c. – interjay May 30 '19 at 18:57
  • Cann you explain what you meant by this - Big O describes the asymptotic behavior (up to multiplication by a constant) for large values of n.???? – Spindoctor May 30 '19 at 19:01
  • Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Prune May 30 '19 at 22:18

1 Answers1

3

Big O is not used to compute the number of instructions you are expected to execute. For a given n, calculating the square root of n will not give you the exact number of times the instruction executes. Big O describes what happens with your function as input size gets very large. Analysis of your function when n is 10 or even 100 does not apply to Big O.

When we say a function's time complexity is O(sqrt(n)), we mean that the function belongs in a class of functions where the time required is proportional to the square root of the value of n, but only for very large values of n.

If you watch the video, the instructor simplifies the k(k+1) / 2 term to k^2 by taking the leading term, because the k term becomes insignificant compared to the k^2 term, when k is very large.

Peter Cheng
  • 758
  • 7
  • 9