Determining Big O Notation

An easier way

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »

53 Replies - 116828 Views - Last Post: 02 March 2013 - 05:43 PM Rate Topic: -----

#1 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,136
  • Joined: 14-September 07

Determining Big O Notation

Posted 12 September 2009 - 02:32 PM

*
POPULAR

This is a subject many people are afraid of, or simply don't get. At first, it seems to be mystical hocus-pocus, but today I'll show you a simple way to quickly get an estimate of the Big O of an algorithm/function. This is not the only way to determine Big O, nor do I make any claims of it being 100 percent accurate or effective. The idea here is to be able to look at loops, functions, and code in general, in a different light.

First, a definition:

Quote

In mathematics, computer science, and related fields, big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. Big O notation allows its users to simplify functions in order to concentrate on their growth rates: different functions with the same growth rate may be represented using the same O notation.


The wiki article from which this is taken is an excellent reference if you need to quickly know the Big O of common/popular algorithms. What it absolutely fails to do is explain how one determines the actual Big O [I will use this term interchangeably with upper bound or limit]. For those not mathematically inclined, their eyes probably glaze over when reading the symbol infested portions. At running the risk of repeating myself, this article is simply here to show another way, one I think is easier (i.e. you could have a solid grasp on the concept without ever taking Calculus).

Some Basic Rules:


1. Nested loops are multiplied together.
2. Sequential loops are added.
3. Only the largest term is kept, all others are dropped.
4. Constants are dropped.
5. Conditional checks are constant (i.e. 1).

That's it really. I used the word loop, but the concept applies to conditional checks, full algorithms, etc.. since a whole is the sum of its parts. I can see the worried look on your face, this would all be frivolous without some examples[see code comments]:

//linear
for(int i = 0; i < n; i++) {
	cout << i << endl;
}



Here we iterate 'n' times. Since nothing else is going on inside the loop (other then constant time printing), this algorithm is said to be O(n). The common bubble-sort:

//quadratic
for(int i = 0; i < n; i++) {
	for(int j = 0; j < n; j++){
		//do swap stuff, constant time
	}
}



Each loop is 'n'. Since the inner loop is nested, it is n*n, thus it is O(n^2). Hardly efficient. We can make it a bit better by doing the following:

//quadratic
for(int i = 0; i < n; i++) {
	for(int j = 0; j < i; j++){
		//do swap stuff, constant time
	}
}


Outer loop is still 'n'. The inner loop now executes 'i' times, the end being (n-1). We now have (n(n-1)). This is still in the bound of O(n^2), but only in the worst case.

An example of constant dropping:
//linear
for(int i = 0; i < 2*n; i++) {
	cout << i << endl;
}



At first you might say that the upper bound is O(2n); however, we drop constants so it becomes O(n). Mathematically, they are the same since (either way) it will require 'n' elements iterated (even though we'd iterate 2n times).

An example of sequential loops:

//linear
for(int i = 0; i < n; i++) {
	cout << i << endl;
}

//quadratic
for(int i = 0; i < n; i++) {
	for(int j = 0; j < i; j++){
		//do constant time stuff
	}
}



You wouldn't do this exact example in implementation, but doing something similar certainly is in the realm of possibilities. In this case we add each loop's Big O, in this case n+n^2. O(n^2+n) is not an acceptable answer since we must drop the lowest term. The upper bound is O(n^2). Why? Because it has the largest growth rate (upper bound or limit for the Calculus inclined).

Finite loops are common as well, an example:

for(int i = 0; i < n; i++) {
	for(int j = 0; j < 2; j++){
		//do stuff
	}
}


Outer loop is 'n', inner loop is 2, this we have 2n, dropped constant gives up O(n).

In short Big O is simply a way to measure the efficiency of an algorithm. The goal is constant or linear time, thus the various data structures and their implementations. Keep in mind that a "faster" structure or algorithm is not necessary better. For example, see the classic hash table versus binary tree debate. While not 100% factual, it often said that a a hash-table is O(1) and is therefore better then a tree. From a discussion on the subject in a recent class I took:

Quote

Assuming that a hash-table is, in fact, O(1), that's not quite true. Being O(1) makes the hash-table superior to a tree for insertion and retrieval of objects. However, hash-tables have no sense of order based on value, so they fall short of trees for searching purposes (including things like "get maximum value").

That said, hash-tables aren't purely O(1). Poor choices in hash algorithm or table size, and issues like primary clustering, make operations on hash-tables in worse-than-constant time in reality.

The point is, saying "hash-tables are superior to trees" without some qualifications is ridiculous. But then, it doesn't take a genius to know that sweeping generalizations are often problematic.


The above is always something good to keep in mind when dealing with theoretical computer science concepts. Hopefully you found this both interesting and helpful. Happy coding!

Is This A Good Question/Topic? 15
  • +

Replies To: Determining Big O Notation

#2 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,136
  • Joined: 14-September 07

Re: Determining Big O Notation

Posted 12 September 2009 - 05:03 PM

*
POPULAR

I noticed I didn't provide a log(n) or nlog(n) example, arguably the toughest ones.

A quick metric to see if a loop is log n is to see how the counter increments in relationship to the total number of elements.

Example:


for(int i = 0; i < n; i *= 2) {
	cout << i << endl;
}



There are n iterations, however, instead of simply incrementing, 'i' is increased by 2*itself each run. Thus the loop is log(n).

An example of nested loops:

for(int i = 0; i < n; i++) { //linear
	for(int j = 1; j < n; j *= 2){ // log (n)
		//do constant time stuff
	}
}



This example is n*log(n). (Remember that nested loops multiply their Big O's.)
Was This Post Helpful? 10
  • +
  • -

#3 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2857
  • View blog
  • Posts: 10,960
  • Joined: 15-July 08

Re: Determining Big O Notation

Posted 20 September 2009 - 09:49 AM

Great tutorial Kya! Thanks a million!

This post has been edited by Dogstopper: 20 September 2009 - 09:49 AM

Was This Post Helpful? 0
  • +
  • -

#4 YamNad  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 9
  • View blog
  • Posts: 120
  • Joined: 11-July 09

Re: Determining Big O Notation

Posted 30 September 2009 - 08:12 AM

Very helpful.

Thanks KYA. :)
Was This Post Helpful? 0
  • +
  • -

#5 cfakhar  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 16-November 09

Re: Determining Big O Notation

Posted 16 November 2009 - 07:54 AM

for(int i = 0; i < n; i *= 2) {
	cout << i << endl;
}



A Big O thanks KYA for your tutotial. I am a novice in this field and have got lot from this post. will you please simplify Big O notation for the function 'logn + 3n'. Got confused from two different books one is mentioning it as O(logn) and the other O(n).

:wub: And one more thing is that don't you think the above code will run for infinite times as the value of i will never incremented by i *=2, because everytime i=0. Will it be like :

for(int i = 1; i <= n; i *= 2) {
	cout << i << endl;
}



If I am wrong, please explain.
Was This Post Helpful? 0
  • +
  • -

#6 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,136
  • Joined: 14-September 07

Re: Determining Big O Notation

Posted 16 November 2009 - 07:56 AM

The top one will run infinitely.


The bottom one is logn since i is incremented by twice itself each iteration.


O(n) would be if 'i' is incremented by one each time.
Was This Post Helpful? 0
  • +
  • -

#7 polens  Icon User is offline

  • D.I.C Head

Reputation: 13
  • View blog
  • Posts: 155
  • Joined: 09-November 09

Re: Determining Big O Notation

Posted 22 November 2009 - 06:11 AM

sir need help here....

i am very lost here....
i am using JAVA NETBEANS....
i am making a program that gets the Frequency count and Big-O of an algorithm using buffered reader to get the problem in a text file and then solve the problem...
any one can help me guys....
thanks in advance!!!
Was This Post Helpful? 0
  • +
  • -

#8 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,136
  • Joined: 14-September 07

Re: Determining Big O Notation

Posted 22 November 2009 - 12:35 PM

Open up a thread in the java forums with your attempt/problem.
Was This Post Helpful? 0
  • +
  • -

#9 xrisanthi  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 24-January 10

Re: Determining Big O Notation

Posted 24 January 2010 - 12:20 PM

I need to calculate the O notation for this block
-----------------------------------------------------
for(int i = 0; i < n; i++)
  for for(int j = 0; j < n; j++)

   statements1.....
     for(int k = 0; k< 60; k++)
        for(int l = 0; l < 10; i++)
           statements2....
          end l;
      end k;
    for(int g = 0; i < n; g *= 10) 
      for(int h = 0; i < n; h *= 10) 
             statements 3..........
        end h;
     end g;

end j;
end i;

----------------------------------------

I have understood that if everything ended after the second set of statements I would have O(n^2 x 60 x 10)= O(n^2) but then the other for loops make everything so confusing.
Would it be O (n^2 * log(n) *log(n))?

Any help would be appreciated!

This post has been edited by NickDMax: 21 January 2011 - 09:37 AM

Was This Post Helpful? 0
  • +
  • -

#10 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,136
  • Joined: 14-September 07

Re: Determining Big O Notation

Posted 24 January 2010 - 12:41 PM

n^2 is still a greater growth rate then log(x)^2 so you can drop the lower terms
Was This Post Helpful? 0
  • +
  • -

#11 xrisanthi  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 24-January 10

Re: Determining Big O Notation

Posted 24 January 2010 - 12:43 PM

View PostKYA, on 24 Jan, 2010 - 11:41 AM, said:

n^2 is still a greater growth rate then log(x)^2 so you can drop the lower terms


Ofcourse! Thank you. (that was a pretty quick reply! :^: )
Was This Post Helpful? 0
  • +
  • -

#12 Guest_Marcus Strang*


Reputation:

Re: Determining Big O Notation

Posted 15 March 2010 - 03:46 PM

View PostKYA, on 12 September 2009 - 01:32 PM, said:

//linear
for(int i = 0; i < 2*n; i++) {
	cout << i << endl;
}



In the above example where the counter to 2*n produces O(2N) which is reduced to simply O(N), what about in the following case


for(int i = 0; i < n*n; i++) {
	cout << i << endl;
}



As now it is just a single for loop, but the counter increases to n^2, does this mean the notation for this loop would be O(N^2) ?
Was This Post Helpful? 0

#13 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,136
  • Joined: 14-September 07

Re: Determining Big O Notation

Posted 16 March 2010 - 03:18 PM

That is correct. The loop will iterate n^2 times even though it is just a single loop.
Was This Post Helpful? 0
  • +
  • -

#14 Guest_quophyie*


Reputation:

Re: Determining Big O Notation

Posted 27 March 2010 - 11:44 AM

Hi KYA

I've just come across this post which happens to be the best and easiest explanation of the Big-O that I've come across. I do have a few questions that I hope that you may be able to answer for me.

1)
what will the big-O for the example below be? will it be O(3*4) which is O(12) or something else? if 3 and 4 are constants and hence need to be dropped, what will the big-O be?

for(int i = 0; i < 3; i++) { //linear
        for(int j = 0; j < 4; j ++){ // log (n)
                //do constant time stuff
        }
}



2) From you explanation of the O(LogN), does it mean that whenever a loop's increment is some multiple, its big-O automatically becomes O(logN)?

For example,
        for(int j = 0; j < n; j *= 2){ //seeing as the increment is j=*2, 
                //does this become O(logn) automatically?
                //do constant time stuff
        }



Does the big-O automatically become O(logN)?

3) what will the big-O for the following example be. I'm not sure if the example below is practical in real life but its still something that I'm curious about
        for(int j = 2; j < 4; j /= 2){
                //do constant time stuff
        }



4) Finally in your example below, you use the formula (n(n-1)/2. why is n*(n-1) divided by 2 but in other quadratics, they are not divided by 2?

Quote

//quadratic
for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++){
                //do swap stuff, constant time
        }
}



Outer loop is still 'n'. The inner loop now executes 'i' times, the end being (n-1). We now have (n(n-1)/2). This is still in the bound of O(n^2), but only in the worst case.


Thanks in advance.

Quophyie?
Was This Post Helpful? 0

#15 Guest_quophyie*


Reputation:

Re: Determining Big O Notation

Posted 27 March 2010 - 03:04 PM

Hi KYA

I also have another question with regards to one of the answers that you gave to Marcus Strang with regards to the Big-O of the code snippet below.
for(int i = 0; i < n*n; i++) {
        cout << i << endl;
}


You said that the Big-O is O(n^2). I'm just wondering whether it should not be O(n) instead? I say this because if for instance you substitute 'n' for 3, then your loop will be run exactly nine times i.e. exactly 9 operations should be performed. This is surely linear isn't it? And if that's the case then should the Big-O not be O(N)? No matter the value of n, the number of times the loop will be run will be the result of the multiplication of n*n. Please let me know if my analysis of this is wrong.

Regards

Quophyie
Was This Post Helpful? 0

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »