Time Complexity- For Loop

Question

I have a Question about calculating the time complexity with O-Notation . We have given this Code ..

int a=0; 
For (int j=0; j<n ; j++){ 
    For(int i=0; i*i<j; i++){ 
     a++; } 
}

I think the solution ist O(n^2) That for the first for loop we need n and for the second we need n... but I as I answerd the exam Questions..I got zero points for it

... Also for another code

 int g(int y){ 
  If (y<10){ 
   Return 1;} 
  else { 
    int a=0; 
    for ( int i=0;i<n;j++) { 
        a++;}
      return a+g(2(y/3)+1)+g(2(y/3)+2)+g(2(y/3)+3);}
 }

I think the solution ist O(n) , That the variables time won't be calculated... the if sentence has a constant time O(1) and would be dominated by the for loop and the for loop would have O(n)

.... Also any advises or resources that explains how a program time would be calculated? And thank you :) 😃

Answer 1

For the first code, you have:

T(n) = 1 + sqrt(2) + ... + sqrt(n) = Theta(n\sqrt(n))

As i*i < j means i < sqrt(j). For the second, you can use Akra-Bazzi theorem:

T(n) = T(2n/3+1) + T(2n/3+2) + T(2n/3+3) + n

and reach to T(n) = 3 T(2n/3) + n to use the master thorem (~O(n^2.7))