big o - Calculate the time complexity of the following function -


how calculate time complexity of following function?

int compute (int n) {    int j = 0;    int = 0;    while (i<=n)    {        = 2*j + + 1;        j++;    }    return j-1; } 

now, know loop has o(n) time complexity, in case i grows in faster rate. taking iteration iteration found out that, every m-th iteration i = m^2. i'm still confused how calculate big-o.

if @ values of , j few iterations:

i=1 j=1  i=4 j=2  i=9 j=3  i=16 j=4 

and on. mathematical induction can prove takes square values: ( 2*n + n^2 + 1 = (n+1)^2 )

since loop while i<=n , since takes vales 1, 2^2, 3^2,..., k^2 <=n, means stop when i=k goes on sqrt(n). hence complexity seems o(k) means o(sqrt(n)).


Comments

Popular posts from this blog

toolbar - How to add link to user registration inside toobar in admin joomla 3 custom component -

linux - disk space limitation when creating war file -