Determining the Time Complexity of code

[bona3]

I want to know the time complixity in details for this code

public class
 {

    for (int i = 0; i < limit; i++) 
    {
         d = fun(i)  ;   // call to  function                                           
           m=((i >> d) + 1) >> 1;      
         d3=2 - (num1+ d)%2;           
        s = (m*d3)%3; 
        int dest = (m + d3)%3;         
 cout<<d3<<d2
      }      
  
  

   static int fun(int i)
 {
      int g, x = i+1;
      for (g = 0; x%2 == 0; g++) x /= 2;
      return g;
                    }

} // end of class

[bona3]

and also the time complixity for this code pls

#include <iostream> 
#include <stack> 

using namespace std; 

void output(int value, int from, int to) 
{ 
   char towerNames[3] = {'A', 'B', 'C'}; 
   cout << "Move disc " << value << " from " << towerNames[from] << " to " << towerNames[to] << endl; 
} 

int main() { 
   int n = 0; 
   cout << "Enter number of discs: "; 
   cin >> n; 
    
   stack<int> temp; 
   stack<int> towers[3]; 
   int recent = 0; 
   bool broke = false; 

   cout << "Tower A contains the following discs(from top to bottom): "; 
   for(int i = 0; i < n; i++) { 
      towers[0].push(n-i); 
      cout << (i+1) << " "; 
   } 
   cout << endl << endl; 

   bool isEven = false; 
   if((n % 2) == 0) isEven = true; 

   while((towers[1].size() < n) && (towers[2].size() < n)) { 
      for(int i = 0; i < 3; i++)    { 
         if(!towers[i].empty()) { 
            if(towers[i].top() != recent) { 
               if(isEven) { 
               for(int j = 1; j < 3; j++) { 
                  if(towers[(i+j)%3].empty()) { 
                     towers[(i+j)%3].push(towers[i].top()); 
                     recent = towers[i].top(); 
                     output(towers[i].top(),i,(i+j)%3); 
                     towers[i].pop(); 
                     broke = true; 
                     break; 
                  } 
                  else if(towers[(i+j)%3].top() > towers[i].top()) { 
                     towers[(i+j)%3].push(towers[i].top()); 
                     recent = towers[i].top(); 
                     output(towers[i].top(),i,(i+j)%3); 
                     towers[i].pop(); 
                     broke = true; 
                     break; 
                  } 
               } 
               } 
               else { 
               for(int j = 2; j > -1; j--) { 
                  if(towers[(i+j)%3].empty()) { 
                     towers[(i+j)%3].push(towers[i].top()); 
                     recent = towers[i].top(); 
                     output(towers[i].top(),i,(i+j)%3); 
                     towers[i].pop(); 
                     broke = true; 
                     break; 
                  } 
                  else if(towers[(i+j)%3].top() > towers[i].top()) { 
                     towers[(i+j)%3].push(towers[i].top()); 
                     recent = towers[i].top(); 
                     output(towers[i].top(),i,(i+j)%3); 
                     towers[i].pop(); 
                     broke = true; 
                     break; 
                  } 
               } 
               } 

            } 
         } 
         if(broke) { broke = false; break; } 
      } 
   } 

   cout << endl << "Tower C now contains the following discs(from top to bottom): "; 
   while(!towers[2].empty()) { 
      cout << towers[2].top() << " "; 
      towers[2].pop(); 
   } 

   return 0; 
}

[newb16]

For the first average complexity of fun() is constant equals 2.
The second it too long, didn't read it but it's looks Towers of Hanoi problem and its complexity is explained e.g. in wikipedia article.

[Ectara]

Also, using the code tag would help others read it and provide help.

[bona3]

okay , thank you for your help

If you can help me to calculate the 1est code complixity

[donbock]

Your first post asked for time complexity, but your most recent post asked for code complexity. Do you want ...

• result of a static analysis of the program; akin to Cyclomatic Complexity?
• rough estimate of the execution time (computational complexity); akin to O(N^2)?

[bona3]

thankyou donbock but I mean time complexity ,

[donbock]

Please be a little more forthcoming.

How do you need to report time complexity? Personally, I am most familiar with Big-O notation; for example O(1), O(N), O(logN), O(NlogN), O(N^2), and so on. Is that what you want?

[bona3]

yes,Big-O notation , thankyou very much for your help

[donbock]

I've reprinted the code from your first post with a couple of changes. I'm only looking inside the public class braces because I don't do C++; I replaced the call to 'fun' by the contents of that function to simplify the analysis; and I replaced 'limit' with 'N' to match big-O notation.

for (int i = 0; i < N; i++)  
{
   int g;
   for (g = 0,x=i+1; x%2 == 0; g++)
   {
      x /= 2;
   }
   d = g;                                         
   m=((i >> d) + 1) >> 1;       
   d3=2 - (num1+ d)%2;            
   s = (m*d3)%3;  
   int dest = (m + d3)%3;          
   cout<<d3<<d2 
}

Big-O notation is primarily interested in counting loop interations. There are two loops.

• The outer for-loop obviously executes N times.
• The inner loop is the tricky one. How many times do you think it executes for each value of i+1?

You need to participate in finding the solution.

[bona3]

okay let me think , if we can write the i+1 as 2^n , so we will execute the iner loop n times , I mean when i=3 -> i+1=4 ->2^2 , so we will execute the innner loop 2 times , otherwise if the number is dividable by 2 but we cant write it as 2^n we will execute it 1 times ,

[donbock]

okay let me think , if we can write the i+1 as 2^n , so we will execute the iner loop n times , I mean when i=3 -> i+1=4 ->2^2 , so we will execute the innner loop 2 times , otherwise if the number is dividable by 2 but we cant write it as 2^n we will execute it 1 times ,

What about, for example, i+1=24. This isn't a power-of-two, but the loop will execute more than once.

Hint: look at the binary representation of the various values of i+1.

[bona3]

mmmmmmmmmm your greate , the inner loop will execute to (number of zero ) times , I mean 2 =10 -> 1 time , 8=1000->3 times

[newb16]

Now you need to calculate the average number of iterations of the inner loop for numbers from 1 to N.

[donbock]

mmmmmmmmmm your greate , the inner loop will execute to (number of zero ) times , I mean 2 =10 -> 1 time , 8=1000->3 times

That is, the number of loop iterations is equal to the number of trailing zeroes. For example, 20 (binary 10100) will have two iterations.