Determining the Time Complexity of code

bona3

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

Expand|Select|Wrap|Line Numbers

 
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

Expand|Select|Wrap|Line Numbers

 #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.

Expand|Select|Wrap|Line Numbers

 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

Quote:

Originally Posted by 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 ,

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

Quote:

Originally Posted by bona3

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.

bona3

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

donbock

Quote:

Originally Posted by bona3

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

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

Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

re: Determining the Time Complexity of code

Similar C / C++ bytes

/bytes/development

/bytes/it

/bytes/about