Finding

You are being asked to do a lot.

Analytical
Count through the code and compute the Big-O and Big-Ω. If they are pretty close to the same thing, then you have a Big-Ɵ. (This is the easy part.)

Big-O (and others) are not interested in constant operations (like *=). They are interested in loops (and recursion, which is a form of loop). In other words, the number of things you do per loop is not important. The number of times you loop is important.

Examples:

int x = 12;  // O(1) — totally unimportant

for (int n = 0; n < N; n++)  // O(N) — this is important!
  x = 12;

for (int n = 0; n < N₁; n++)  // O(N₁) ...
{
  int x = 12;
  for (int m = 0; m < N₂; m++)  // × O(N₂) → O(N₁×N₂) → O(N²) — important!
}

for (int n = 0; n < N; n++)  // O(N) ...
{
  int x = 12;
  for (int m = n; m < N; n++) // × O(log N) → O(N log N) — important!
}

(My explanations aren’t always the best. I just found this SO answer which is brilliant. https://stackoverflow.com/a/2307314/2706707)

Empirical
That’s another word for “observational”. You must construct a number of different inputs designed to try to get both best and worst behavior from the program. Observe the actual behavior and report whether or not the inputs support or contradict your Big-O/Ω/Ɵ analyses.

You would probably be able to just use a simple clock timer to see how long the program takes to complete on a given input. Make sure to push the limits of your program (so that you can overcome the cost of I/O operations).

If you are smart, you might mention that the best case behavior includes the cost of I/O, show that the cost of I/O is the same for both best and worst case behavior (because the same amount of I/O is being done for both cases), then analyze the difference between the best case and all other results.

One last note about time analysis: the first time you run the program will always cost more. Make sure to run each case multiple times in a row. Discount the first time you run each case and average the remaining times to get a mean representative time for that specific case. Impress your professor by putting this in your “Procedures” section and the reasons for doing it.

Hope this helps.

Ok this helps, but we only want to do analysis on the ipow() function. So would line 27 is the basic operations that I could count.

Ah, just ipow(). Okay, still:

Line 27 does not matter.
Lines 24 and 26 matter.

ipow is looks incorrect. anything to the zero power is 1. So if power is 0, return 1.
if base is zero, zero to any power is zero.

since the code does not give the correct result, studying it seems silly.
However, do you understand what it is doing for the computation and what its O() complexity is?

@jonnin

It is wrong, but not quite the way you describe it, and only in normative CS contexts.

  0⁰    → 1
  0^n≠0 → 0 (this is where the function is wrong)
  x⁰    → 1
          _n
  x^n≠0 → ∏ x
         ⁱ⁼¹

So a correction might be:

uint ipow(uint base, uint exp)
{
  if( base == 0 )
    return exp == 0;
  uint result = 1;
  while( exp > 0 )
  {
    if( (exp & 1) == 1 )
      result *= base;
    exp >>= 1;
    base *= base;
  }
  return result;
}

I don’t see how the correctness of the function is an issue for the OP’s assignment. OP might want to correct the function and see if he gets any extra credit for noticing, but it is otherwise immaterial.

The actual value of 0⁰ is an argument older than the lot of us combined (by an several orders of magnitude).

For what it’s worth, I agree with Knuth.

How does the ipow() work?

So would the basic operation be *= or just the exp being compared?

Last edited on

@jlin55
At this point I have answered that very question several times now on this very thread. You need, now, to start paying attention. If you are still unsure what matters when counting stuff for Big-O analysis, you need to start re-reading your class notes, looking around online, and/or making an appointment with your school/university help center and/or your professor for additional guidance.

The purpose of homework like this is to show that you (1) have been paying attention and (2) have taken the time to study and understand the material.

As someone trying really hard to help you on the forum, it becomes very frustrating to keep putting time and effort into answering the same question over and over and over, especially when it comes from the same person.

Because I don’t want to just drop you, here is some additional reading that may help:
http://www.cplusplus.com/forum/beginner/222245/#msg1019594
https://www.google.com/search?q=big+o+notation

just in case the question is just about the murky c syntax:
>> is the bit shift operator. If you think about it, x cubed is against 3. 3 in binary is 11, or 2+1
and x cubed is x*x*x or x squared times x, which looks a lot like 3 in binary, eh? This is NOT by chance.
x to the 5th is x squared * x squared * x. What is 5 in binary? 4+1 ... and what is 4? 2*2 ...

I made a recent post on making an int power function and boiled it down to 16 multiplies for 64 bit ints (exploiting that 2^64 is the biggest we can store) I think .. I slept since then. Does that ... lead to any thoughts about the big-O difficulty of the problem?

Take it from there. Play computer with it... or compile it and add a bunch of cout statements... diagnose it and figure out how it works. You can't do analysis of something until you understand what it is doing!!!

by the way the same code will do for doubles to an integer power, and even complex etc. Its the power that governs the problem, not the base.

And the above is more correct. I mis-spoke saying anything to 0 is 1. That was an oversimplification. Regardless, the code is wrong. Performance analysis of buggy code is futile. Performance tuning is the last thing you do once the code actually works. Here, that is minor (the fixes are not going to affect run-time) but it is still a good rule to live by. I can always get you the wrong answer faster if that is ok!

Last edited on

@Duthomhas Sorry about it.

This is what I have so far. I counted the comparison in the inner if statement. I implement the cout and cerr statements down below in my main and got two compiler errors.

Last edited on

the function can't see basic ops from main. Given what you are doing, I would make it global (outside main). You could modify the function and pass it in, but there are times to "cheat" and given your need, this is a good place to do just that.

weights is a vector. Ipow takes an int. You either need weights[index] or weight here.

you are ALSO only counting when it is true. You need to count the false also, that is still a comparison.

The value you have is how much "work" the loop does, which is critical to know.
also, the ONLY statement in your if is now the counter. You need {} around it or you have badly broken the code.


int basic_ops = 0; //remove from main
int count_comps = 0;

uint ipow(uint base, uint exp)
{
  if( base == 0 )
    return 1;
  uint result = 1;
  while( exp > 0 )
  {
    countcomps++; //the # of loop iterations and comparisons, both
    if( (exp & 1) == 1 ) //count the work done
      {
       basic_ops++;
      result *= base;
      }
    exp >>= 1;
    base *= base;
  }
  return result;
}

Last edited on

Why would you do count_ops? I am looking for only the best basic operation there is in the ipow().

you said it was a count of comparisons, but you were only counting the successful comparisons, not all of them. I don't personally care what you count, so you can do what you need to get the answer you want. I was much more concerned with you breaking the code with your counter than what you actually wanted to count.

Well I wasn't looking for count of comparisons, which is my bad. I was looking for the best basic operation (best action) in that function.

Here is what I have so far:

Last edited on

@Duthomhas I was told that we can count in the main function