[imu_1]

The question is to find the Big-O of the following by giving reason(s) :
Assume numItems plays the role on N.

if ( num < numItems )
for (int i=0; i<numItems; i++)
{
System.out.println(i);
}
else
System.out.println("too many");

Ok, I would say that this method runs in O(n) because the if statement is O(1), the for loop is O(n) (runs N times).

So then, since O(n) > O(1) , the answer is O(n).

Is this right? Any ideas?

[blackcompe]

Yup.

if ( num < numItems ) - O(1)

for (int i=0; i<numItems; i++) - O(n)

System.out.println("too many"); - O(1)

If the condition is true, it's O(n) + O(1) = O(n + 1) = O(n).
If it's false it's O(1) + O(1) = O(2), which is O(n).

This post has been edited by blackcompe: 11 September 2011 - 05:09 PM

[imu_1]

Alright,thanx alot man.Looks like you know this thing inside out...inspiring!!!

K here are two more of these:

int i = numItems;
while (i > 0)
i = i / 2; // integer division will eventually reach zero

I would say this is O(Logn) because it takes O(1) time to cut the problem size by a fraction (1/2).

I would appreciate if you(or anyone else) share your thoughts on this.

Also,what if it was like this:

while (i > 0)
System.out.println("Infinity");
Will this have a running time ? May be O(infinity) ? What do you think?

[blackcompe]

Quote

int i = numItems;
while (i > 0)
i = i / 2; // integer division will eventually reach zero

I would say this is O(Logn) because it takes O(1) time to cut the problem size by a fraction (1/2).

Yup. It's O(log(n)) because i is halved each iteration. Suppose i is 100:

1st itr: i = 50
2nd itr: i = 25
3rd itr: i = 12
4th itr: i = 6
5th itr: i = 3
6th itr: i = 1
7th itr: i = 0

So the loop executes 7 times, where an atomic comparison and a division operation is done. Disregard the constant operations and it's O(7), which is <= O(log(100)) = O(10).

Quote

while (i > 0)
System.out.println("Infinity");
Will this have a running time ? May be O(infinity) ? What do you think?

Good question. I guess it's O(∞). Here's a small discussion on a similar question. You'll probably get a good answer at cstheory.stackexchange.

This post has been edited by blackcompe: 11 September 2011 - 05:58 PM

[imu_1]

Thanks alot man, i lke the way you comined O(n) and O(logn) in your illustration.How about the second one?(The infinity one?)

Here it is:


Also,what if it was like this:

while (i > 0)
System.out.println("Infinity");
Will this have a running time ? May be O(infinity) ? What do you think?

oww u answered it. Thanks

[blackcompe]

No problem!

[imu_1]

Ok, here's something trick I would say:

If p1(N) = 5N and p2(N) = 6N, why are both p1(n) and p2(n) O(N), since for N>=1, 6N is larger than 5N?

My answer: I would say that both functions are linear functions, and all linear functions take linear time algorithm. In this case, 6n grows approxiamtely twice as large as 5n for large values of n. This is a typical characteristic of linear function.That is why is is O(n)....

What do you say?

[blackcompe]

Quote

If p1(N) = 5N and p2(N) = 6N, why are both p1(n) and p2(n) O(N), since for N>=1, 6N is larger than 5N?

My answer: I would say that both functions are linear functions, and all linear functions take linear time algorithm. In this case, 6n grows approxiamtely twice as large as 5n for large values of n. This is a typical characteristic of linear function.That is why is is O(n)....

The short answer is that you can disregard all constants in the highest order term when doing CC analysis, and therefore they're both O(n).

E.g. Suppose I have f(n) = 7n³ + 98n² + 2343n + 343433

7n³ is the highest order term (the term with the greatest exponent). You can completely disregard all other terms because it dominates them at some n₀ (it's grows a lot faster; it's what gives the graph its shape). So, you end up with f(n) = 7n³. You can also get rid of the constant factor, because it too is dominated by n³. Multiplying by a constant isn't going to affect the function's growth, it may displace it's graph, but the shape of graph doesn't change. Finally, you get f(n) <= n³ or f(n) is O(n³). That's just the quick and dirty way to find the complexity.

The more detailed answer can be understand by looking at the formal definition of Big-O:





Let f(n) = 5n and g(n) = n

So, f(n) = 5n <= M(g(n)) = M(n) for M >= 5 and n₀ = {N} (All natural numbers)

It's the same with 6n.

Let f(n) = 6n and g(n) = n

So, 6n <= M(n) for M >= 6 and n = {N}.

We just showed they are both bounded by f(n) = n, so they are both O(n).

This post has been edited by blackcompe: 12 September 2011 - 11:21 AM

[mojo666]

imu_1, on 11 September 2011 - 06:44 PM, said:

Also,what if it was like this:

while (i > 0)
System.out.println("Infinity");
Will this have a running time ? May be O(infinity) ? What do you think?

I'm no expert, so take my answer with a grain of salt.

I would say it is O(1).

Big O notation relies on variability. If I write an algorithm that takes 1 minute for 10 customers, I want to know if it will still be efficient when I run the algorithm over 100 customers a few years later. If the algorithm is O(n), then yes, it will take about 10 minutes. If it is O(2^n), then it will take about 2^90 minutes, and I just don't have that kind of patience.

The algorithm in question doesn't really rely on any variable. It's kind of like asking how long an algorithm that solves chess will take. Since there is only one possible input (the starting position), the answer is O(1) even though such an algorithm would take billions of years. Even though we have a variable i, it takes the same amount of time to complete if i is 1 or 1000000000. No variablility means constant run time.

[sepp2k]

I disagree. According to the definition of the O notation the algorithm's runtime being O(1) would mean that there are constants c and N, such that for all i>N the algorithm's runtime is less than or equal to c. However since the algorithm's runtime is infinite, there is no such constant, so it's not in O(1).

Since the same logic can be applied to disproof the runtime being in O(f(n)) for any real function f, This means that the algorithm's runtime simply is not in any O.

I suppose we could say it's in O(infinity) to express this, but that's certainly not covered by the definition (though I'd imagine everyone would understand what it's supposed to mean anyway).

[mojo666]

sepp2k, on 12 September 2011 - 11:52 AM, said:

I disagree. According to the definition of the O notation the algorithm's runtime being O(1) would mean that there are constants c and N, such that for all i>N the algorithm's runtime is less than or equal to c. However since the algorithm's runtime is infinite, there is no such constant, so it's not in O(1).

Take the following programs

/***prog 1****/
print "Hello World"
/*************/

/***prog 2****/
while(true)
{print "Infinity"}
/**************/

In order for program 1 to formally qualify as a O(1) algorithm then there must be constants c and N such that for all n>N, the algorithms runtime is less than c. The problem is there simply is no meaning for n, so it doesn't meet the formal definition. Yet, we have no problem saying this algorithm is O(1). Program 2 has the same problem. O(1) has a formal definition but we also use it to say "The program runtime is independant of any data". I think the program in question falls into the latter category.

[sepp2k]

I don't quite follow you. Let's says we define print to take 1 step per character in the string, where a step is our measure of an algorithm's runtime. Then print "Hello World" takes 11 steps. So the runtime of the algorithm can be described by the function f(n) = 11. Clearly that function is in O(1).

Now let's consider prog 2. Here the runtime can only be represented by the function f(n) = infinity (ignoring for the moment that that's not a real function). This function is definitely not in O(1) for the reasons I explained in my earlier post.

The important thing to note, I think, is that O(1) does not mean that the algorithms runtime does not depend on the input size, but that it's bounded by a constant, which does not depend on the input size (so the algorithm never takes more than X steps, where X is not dependent on the input). For an algorithm which runs infinitely, there clearly is no such constant, so it's not in O(1).

This post has been edited by sepp2k: 13 September 2011 - 11:21 AM

[elgose]

If an "algorithm" runs infinitely and never terminates, it isn't an algorithm by definition (fails the "finiteness" qualification). So, we're arguing over Big-O of an algorithm for something that isn't an algorithm.

This isn't a function, either, because f(x)=infinity is just wrong (infinity is not a value). Loosely speaking, f(x) should give some definite y, yet for all numbers n in the set of reals, f(n) is "infinity" implies, it seems, that f(n) is undefined. [Someone with bigger math chops than I might be able to give a more formal proof]

In short, don't sweat it because there is no upper bound for something that isn't an algorithm and isn't a function. Might as well find Big-O of an apple (I'm guessing O(orange)?)

This post has been edited by elgose: 14 September 2011 - 10:04 PM

[sepp2k]

Post retracted because it was quite inaccurate/wrong.

This post has been edited by sepp2k: 15 September 2011 - 03:32 AM