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
Post a Comment