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

It isn't wrong to say the first code is O(n^2) since big-Oh is an upper bound. Its just not very precise — Abhay Aravinda, May 04 '20 at 15:38

OmG · Accepted Answer · 2020-05-04T15:52:31.363

2

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

edited May 04 '20 at 15:52

answered May 04 '20 at 15:33

OmG

18,337
10
57
90

So how did we come to Theta(n/sqrt(n)) ,, so wie said n for the first for loop and sqrt(n) for the second ... therfor the multiplication must be Theta (n^1,5) ? – Sayuri May 04 '20 at 16:06
@Sayuri yes. the first loop is `n` and the inner loop is `sqrt(n)`, so it is `n\sqrt{n}` or `n^1.5`. – OmG May 04 '20 at 17:29

Time Complexity- For Loop

1 Answers1