I have recently understand the Big Oh notation. I have recently came across the example given in the book.
void Function(int n)
{
int i=1 ;
int s=1 ;
while( s <= n)
{
i++ ;
s= s+i ;
print(\*");
}
}
I don't know how does the author arrives at the time complexity of the above algorithm as O(√n). I just want to understand the process for arriving at this conclusion?
It can easily be seen as s is growing quadratic in terms of number of iteration.
s = 1 // set as 1 initially
Now we are adding S = s + i // Where i increasing linearly by one unit in each iteration
//So it's just a addition i.e. s = 1 + 2 + 3 +4 ....+i, which will sum up to s = i(i+1)/2
Hence s = i(i+1)/2 = (i^2+i)/2 where i is the number of iteration.
Now, In i iteration we are getting s = (i^2+i)/2
To get s >=n we required only √n iterations.
Hence the time-complexity of given program will be O(√n).
