Example algorithm time complexity

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 ie 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) .

链接地址: http://www.djcxy.com/p/40042.html

上一篇: 对于大O符号，2 ^ n或n ^ 2中占优势的术语是什么

下一篇: 算法时间复杂度的例子