# Determining Big-O

Page 1 of 1## 13 Replies - 2169 Views - Last Post: 15 September 2011 - 02:25 AM

### #1

# Determining Big-O

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 Big-O

### #2

## Re: Determining Big-O

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 Big-O

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 Big-O

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 Big-O

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 Big-O

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 Big-O

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 Big-O:

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 Big-O

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 Big-O

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 Big-O

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 Big-O

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 Big-O

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 Big-O of an apple (I'm guessing O(orange)?)

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

### #14

## Re: Determining Big-O

Posted 15 September 2011 - 02:25 AM

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