Some Big O notation help needed

[justinbailey]

I have to answer with the runtime for Big O for a few examples of C++ code. I'm generally having some trouble grasping the concept of Big O but two particular problems are stumping me:

cin >> x;

   double n = example(x);
      
for ( i =0; i << n; i++)
      {
             cout << i + 100;

      }


      double example(int j)
      { return j * j; }

and

cin >> n;
	k = 1;
	do
	{
	  j = 1;
	  do
	  {
		.
		.
		j = 2 *j;
	  }while (j <= n);
	  k++;
	}while(k <= n);

What stumps me in particular on the top one is the return statement (my other problems don't feature it), and the bottom one has a do-while loop which the other problems also don't have. How would I go about tackling these problems?

[VernonDozier]

You tackle it by keeping a tally of the number of times you go through the loop for a given n, then finding a pattern and making a math program from it. So assign n to equal 1 and figure out how many times the cout statement displays. The do it for 2. Then 3. Then 4, etc.

Then if you have a table like this:

n f(n) 1 1 2 4 3 9 4 16

f(n) equals n^2, so O(n) = n^2. It's a math problem. Get your table and calculate a function for f(n) based on the points and you should have your O(n).

[justinbailey]

You tackle it by keeping a tally of the number of times you go through the loop for a given n, then finding a pattern and making a math program from it. So assign n to equal 1 and figure out how many times the cout statement displays. The do it for 2. Then 3. Then 4, etc.

Then if you have a table like this:

f(n) equals n^2, so O(n) = n^2. It's a math problem. Get your table and calculate a function for f(n) based on the points and you should have your O(n).

That should help! Thanks.