Determining BigO
Page 1 of 113 Replies  1504 Views  Last Post: 15 September 2011  02:25 AM
#1
Determining BigO
Posted 11 September 2011  04:53 PM
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?
Replies To: Determining BigO
#2
Re: Determining BigO
Posted 11 September 2011  05:08 PM
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
#3
Re: Determining BigO
Posted 11 September 2011  05:44 PM
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?
#4
Re: Determining BigO
Posted 11 September 2011  05:53 PM
Quote
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
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
#5
Re: Determining BigO
Posted 11 September 2011  05:59 PM
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
#7
Re: Determining BigO
Posted 11 September 2011  06:10 PM
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?
#8
Re: Determining BigO
Posted 11 September 2011  06:26 PM
Quote
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^{3} + 98n^{2} + 2343n + 343433
7n^{3} 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_{0} (it's grows a lot faster; it's what gives the graph its shape). So, you end up with f(n) = 7n^{3}. You can also get rid of the constant factor, because it too is dominated by n^{3}. 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^{3} or f(n) is O(n^{3}). 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 BigO:
Let f(n) = 5n and g(n) = n
So, f(n) = 5n <= M(g(n)) = M(n) for M >= 5 and n_{0} = {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
#9
Re: Determining BigO
Posted 12 September 2011  10:39 AM
imu_1, on 11 September 2011  06:44 PM, said:
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.
#10
Re: Determining BigO
Posted 12 September 2011  10:52 AM
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).
#11
Re: Determining BigO
Posted 13 September 2011  10:30 AM
sepp2k, on 12 September 2011  11:52 AM, said:
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.
#12
Re: Determining BigO
Posted 13 September 2011  11:18 AM
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
#13
Re: Determining BigO
Posted 14 September 2011  10:03 PM
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 BigO of an apple (I'm guessing O(orange)?)
This post has been edited by elgose: 14 September 2011  10:04 PM
#14
Re: Determining BigO
Posted 15 September 2011  02:25 AM
This post has been edited by sepp2k: 15 September 2011  03:32 AM
