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?

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 …

## All 2 Replies

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

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.