Example algorithm time complexity

Question

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?

Shravan40 · Accepted Answer · 2014-11-21 12:25:57Z

2

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

edited Nov 21, 2014 at 12:25

answered Nov 21, 2014 at 11:52

Shravan40

10.1k6 gold badges33 silver badges51 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Beast Over a year ago

I don't understand how you identify that s=i(i+1)/2 ? is there any mathematics topics that needs to be read for this ? How does it become O(√n).Apology for asking too many questions but I am putting my all efforts to understand the time complexity analysis.

Shravan40 Over a year ago

I have edited the answer, see if you can understand.

Beast Over a year ago

Thanks Shravan. I got that how do you ge that expression s=(i^2+i)/2.But I dont' understand how does it become O(√n). Apology once again for eating your head.

tchrikch Over a year ago

@Beast so s=(i^2+i)/2 and you want s=>n which is the same as (i^2+i)/2 >=n . Please note that i denotes the number of times that loop will be executed since you increase it by 1 each time. The (i^2+i)/2 >=n inequality is quadratic and (for simplicity) you can reduce it to i^2>=n => i>=√n.

Shravan40 Over a year ago

I would say no, if you understand the basic concept of mathematics like A.p, G.P, recursion, Logrithm and polynomial functions. You can see this book cs.princeton.edu/courses/archive/fall07/cos433/mathcs.pdf if you really want something.

|

Collectives™ on Stack Overflow

Example algorithm time complexity

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related