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]

@bona3
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]

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

[bona3]

okay lets complete the solution coz I have to submit the home work tomorrow

[donbock]

@bona3
Then you had better follow newb16's advice. You can either do that analytically (solve the numerical sequence) or empirically (list values of i+1 from 1 to something manageable, put the number of iterations in the next column, put the average value of the first row to the current row in the next column, and try to recognize a pattern).

I will point out that the number of trailing zeroes has to be less than the number of bits; and the number of bits is O(logN). Adding in the effect of the outer loop we find that the time complexity of your function is less than O(NlogN). But don't settle for this approximate answer ... spend a little time working as outlined above and you should get the right answer.

[bona3]

thankyou very much for both of you