[Ghoser777]

Hey, I'm looking in a programming book of mine (Litvin's Java Methods AP book to be exact) and I'm a little confused on the Big-O explanation for a given algorithm (I modified it only slightly):

Code:

public boolean[] toBinDigits(long n)
{
    boolean[] array = new boolean[100];
    int i = 99;
   
    while(i >= 0 && n > 0)
    {
        if(n%2 == 0)    array[i] = true;
        else    array[i] = false;

        i--;
        n/=2;
    }

    while(i>=0)
    {
        array[i] = false;
        i--;
    }

    return array;
}

Now, my initial guess was going to be O(log(n)) because it does keep diving the size of the set by 2. But then I realized that the combination of both while loops together gives 100 iterations every time. So that seems to be O(1).

Another thought I had was to look at the code in another light:

t(n) = tinit + (log(n))*6 + (99 - log(n))*3

So, that means O(log(n)) time, right? If I were to throw in three more operations/assignments/comparisons in the second while loop, would it then be constant time?

Thanks,
Matt Fahrenbacher

[larkost]

This is simple O(1):

You have two while loops in series sharing a single counter variable. The first loop starts counting down from 99, and then leaves off at some point, at which the second one begins. When it reaches 0, you are done. Nothing is ever added to the counter, and for every trip though one of the while lops you loose only one off the counter.

There is nothing in this snippet that is O(log(n)). Everything is O(1), and there are no nested loops or goto's, so this has to be O(1). If you are having problems with this exercise, then you are going to hit a wall very soon.

[Ghoser777]

Here's the thing:

I said it was O(1) in front of my AP class, the Litvin website claims it's O(log(n)), so I look like a moron in front of my students. So either Litvin is wrong or we're both wrong.

I agree with your analysis - that's the way I would think about it. But Litvin claims I'm wrong and I need to figure out if he's crazy or if I'm crazy.

Thanks,
Matt Fahrenbacher

[itai195]

It's constant time, O(1), because it always makes 100 loops.

[Ghoser777]

Okay, 2 votes for me. I should have made this a poll. At least I know I won't be hitting the wall soon

Thanks,
Matt Fahrenbacher

[larkost]

You don't need a poll, this is a straight-forward thing. I am a little concerned if you are teaching AP computer science and don't know this right off bat. This is very basic Big-O theory.

If you are having any problem understanding this at all, simply start trimming anything out of the algorithm that is not directly related to looping, nesting, function/message calls, or goto/labels. This should be like factoring in Algebra, something that just comes naturally. Doing that you get:

Code:
long n = /* something */;
int i = 99;
while(i >= 0 && n > 0) {
    i--;
    n/=2;
}
while(i>=0) {
     i--;
}

And the sudo-code for this:

Code:
take some long number
set a counter to 99
repeat until the counter goes to zero, or you run out of bits in that long number:
    shift the long number so that the least significant bit drops off

repeat for the rest of the counter

As I said before, if this is not readily apparent to you, you should not be teaching Computer Science. This is like a math teacher not getting the joke: "there are 10 types of people in the world: those who can count in binary, and those who can't". In other words, it speaks to a profound lack-of-understanding about a fundamental part of the normal CompSci curriculum.

[Ghoser777]

I appreciate your faith in my abilities.

Anyway, I was damn sure in front of my class that it should be O(1), and they told me I was wrong according to Litvin and I got debased. I'm still waiting for his response back on why he thinks it should be the other way.

Matt Fahrenbacher

[Ghoser777]

Okay, I'm convinced he's confused about the question himself and misses the point in his response to me:

Big-O questions always make artificial assumptions: they only work for an abstract model. One of the assumptions is that numbers have infinite range, even though in reality they are limited. Without this assumption, all big-O questions would have the same answer, O(1), because any loop would be limited by the maximum possible number of iterations. In

for (int i = 1; i < n; i *=2 ) ...

the maximum number of iterations is 31 and in

for (int i = 0; i < n; i++) ...

the maximum number of iterations is 2^31, but there is no fundamental difference here. The convention is that the former loop is O(log n) and the latter is O(n). See, for example, MC question AB 5 in the course description. (The assumption about the infinite int range contradicts the other assumptiuon, that all arithmetic operations on integers take constant time... But that's how the model goes.)

Believe me, I'm convinced that the algorithm is O(1). I just want to find out why Litvin thinks it's O(log(n)) - no reason to fear for my AP students. They just learn a valuable lesson on Monday: don't always trust the book. My whole concoction of t(n) = blah blah blah was made to try to justify Litvin, because it was the only thing that was working in my head. I have cleanly flushed it out.

There's plenty of excellent calculus teachers who get confused from time to time... alright, do I think I've covered my ass enough by now? Sure.

Thanks all,
Matt Fahrenbacher

[Ghoser777]

He hasn't responded to my last email yet, but I think I know what's going on - he coded one thing and meant another.

Essentially, he shouldn't have used a damn counter and used a linked structure or something

Code:
public LinkedList toBinary(long n)
{
    LinkedList list = new LinkedList();
    while(n > 0)
    {
        if(n % 2 == 0)
            list.add(new Integer(1));
        else
            list.add(new Integer(0));

        n/=2;
    }

    return list; //interesting... the list will be empty if n==0
}

That algorithm is clearly O(log(n)). That is what I think Litvin intended for the algorithm to look like, but he coded it poorly.

Okay, I'm happy.

Matt Fahrenbacher

[Ghoser777]

For the record, he just emailed me back and now agrees with me

Victory!

Matt Fahrenbacher

[itai195]

Goes to show that you don't need to know what you're talking about to write a book... This is a pretty egregious error and I'm surprised it took two e-mail to make the author realize it.