Big O notation
Page 1 of 19 Replies  3147 Views  Last Post: 13 September 2012  03:54 AM
#1
Big O notation
Posted 11 September 2012  10:48 PM
100n + 5 = 0(n)
5n + 3nˆ2 = o(nˆ2)
I may sound like Im all over the map but I am. I'm trying to understand this and I don't understand how this is translated into terms of efficiency of algorithms.
two for loops equal nˆ2. Why?
thanks in advance
Replies To: Big O notation
#2
Re: Big O notation
Posted 12 September 2012  01:25 AM
POPULAR
Quote
 If f(x) is a sum of several terms, the one with the largest growth rate is kept, and all others omitted.
 If f(x) is a product of several factors, any constants (terms in the product that do not depend on x) are omitted.
So for your two examples:
Ex 1)
100n + 5 = O(n), why?
"Rule 1": The largest growth rate is kept. As n (a linear term) is a bigger grow rate than 5 (a constant term), 5 drops. Thus we are left with 100n.
"Rule 2":
Then, as 100 is a constant which is not related with n, we are left with n, therefore the order is O(n)
Now I did the first example, try the second one for yourself
As for the for loop example, let's consider the following (note that it is not always true that looping over two for loops results in O(n²), the performance depends on your algorithm)
for(int i= 0; i< n ; i++){ //Some code for(int i= 0; i< n ; i++){ //Some code } }
So let's assume that the //Some code parts take a constant time (basically constant). Then for the outer for loop I have to run n times a constant. However, we also have an inner loop, which also runs n times. Thus for each step in the outer loop we have to run n steps in the inner loop. This continues till the outer loop reaches n.
Thus n*constant (outer loop and the some code part) * (n*constant) (the inner loop part) = c²*n²
Which results in O(n²) after applying the proposed rules.
Hope this helps you out
This post has been edited by karabasf: 12 September 2012  01:27 AM
#3
Re: Big O notation
Posted 12 September 2012  03:17 AM
#4
Re: Big O notation
Posted 12 September 2012  08:10 AM
healix, on 12 September 2012  07:48 AM, said:
100n + 5 = 0(n)
5n + 3nˆ2 = o(nˆ2)
n^2 + 5n and 5n + 3n^2 are O(n^2), not o(n^2). Capital O. To be o(n^2) they'd need to be in O(n) or O(n log n) or something else that's less than n^2.
Quote
As karabasf said, that really depends on the loops and their relation to each other. If you want to reason about the runtime of a loop, you need to consider two things:
a) How many times will the loop execute?
b) How much time will it take for each iteration of the body to execute?
If the number of iterations is x and the runtime of the body is y, then the total runtime of the loop is x*y.
If you have a loop of the form for(int i = 0; i<n; i++), then clearly it will execute n times (assuming neither i nor n are changed inside the loop body). So if the body is a simple operation that only takes a constant amount of time (let's call that amount c), the total runtime is c*n, which is in O(n) (because as karabasf pointed out, constant factors don't matter). If the body is another loop and that loop also goes from 0 to n, then the body of that loop will execute a total of n*n times. So if that body takes a constant amount of time, the total cost will be n*n*c, which is in O(n^2).
However if you have two loops that execute after each other (not inside of each other), then the total runtime is T1+T2 where n is the runtime of the first loop and T2 the runtime of the second. So assuming both loops take O(n) time, the total runtime is O(n+n) = O(n).
Then of course a single loop could also take quadratic time, if it iterates from 0 to n*n instead of from 0 to n.
And of course if you have two nested loops where the outer loop iterates from 0 to n and the inner loop iterates from 0 to 42 and the inner body takes constant time, the total runtime will be O(n).
#5
Re: Big O notation
Posted 12 September 2012  08:34 AM
So for #1:
f(n) = 100n + 5
g(n) = n
Is there some constant so that C*g(n) >= f(n) at some point k? What if C = 101? That would satisfy the definition of BigO, hence why f(n) is O(n) here.
Also, KYA has a couple good tutorials on BigO you should check out:
http://www.dreaminco...bigonotation/
http://www.dreaminco...tationpartii/
#6
Re: Big O notation
Posted 12 September 2012  10:47 AM
Quote
Learning and working with the formal definitions will make working with BigO easier, but I will try to provide a general description of what we are trying to acheive with BigO.
The whole point of this notation is to understand how long an algorithm will run in relation to varying input, particularly how efficient it is as the input grows. The reason for this is that input tends to grow (More customers means more records to store and bigger numbers to deal with, ect.) and we would like some confidence that our algorithms will still meet runtime requirements. "n" is our input. It could represent a size of a collection, value of a number, ect. The function inside the BigO notation tells you how long you might expect your algorithm to take. We get the BigO function by getting a rough count of how many commands are executed. Generally this is the number of times code is repeated multiplied by the number of commands per iteration. You can test this by putting a counter inside the code.
//pseudocode n=5 count=0 for(i=0;i<n;i++) { for(j=0;j<n;j++) { //code count++ } } print count
In the above sample, "count" will always be equal to n^2. It shows you how many times "count++" was executed. The actual runtime will be the number of commands per loop multiplied by "count". However, the actual runtime is not that important. It will vary with "count", so we can just use count to represent our program's efficiency. Afterall, removing one line from whatever is in our "//code" will have little effect on our efficiency because any growth on the input will quickly eliminate the gain. For example, if we were running 4 commands inside the loop, the runtime would be 4 * 5^2 = 100. If we reduce it to 3 commands but the input doubles (setting n to 10), the runtime would be 3 * 10^2 = 300. Our improvement was easily eliminated by the growing input. For the same reason, we drop lower orders when looking at BigO
n=5 count=0 for(i=0;i<n;i++) { for(j=0;j<n;j++) { //code count++ } } for(i=0;i<n;i++) { //code count++ } print count
In this example, count will always be n^2+n, so you might be tempted to say that it is O(n^2+n). However, the effects of the extra "n" are dwarfed by the effects of "n^2" so we tend to ignore lower orders the same way we ignore the exact command count. When n is 5, count is 5^2+5=30. If were were to improve the extra loop to only run in 1/2 the time, then the count would instead be 27 or 28. Now when the input doubles, the new count is 105. Again, the benefits of our improvement are quickly disappearing. For this reason, we only care about the most expensive parts of the algorithm when assesing runtime since that would be the main source of our woes if an algorithm is underperforming. I hope this offered some perspective into the utility of BigO.
#7
Re: Big O notation
Posted 12 September 2012  03:10 PM
If I have a function that is O(nˆ2) and that becomes inefficient do I pick another algorithm to use based on its Big O notation?
Quote
http://www.dreaminco...bigonotation/
http://www.dreaminco...tationpartii/
I checked these out last night but was still confused. The broad idea is there but I'm trying to understand its implementation.
This post has been edited by healix: 12 September 2012  03:11 PM
#8
Re: Big O notation
Posted 12 September 2012  03:33 PM
#9
Re: Big O notation
Posted 12 September 2012  09:48 PM
Quote
Ideally, sure. But only when it truly becomes inefficient, meaning it becomes a bottleneck in your program. As a general rule, you want to avoid optimizing your code before you know what's really slowing things down. With that said, things aren't always as straight forward as simply "This algorithm has O(n), and this one has O(n^2), so obviously I use the first!"
For a basic example, consider array lists and linked lists. If you plan to add/delete data to the end or access random indices, an array list is far better because you can add to the end or access any index in constant (O(1)) time. But to add to the beginning or delete from the beginning, you run into O(n) time. Linked lists are basically the opposite... adding to the front or deleting from the front is O(1), while accessing, adding to the end, or deleting from the end are O(n).
So in this case, if I have to choose between just those two data structures I must look deeper into the type of transactions occur more often and if they occur in a while to act as a bottleneck.
Also keep in mind CS takes some liberties in the definition of BigOh. By definition, something that is O(n) is also O(n^2), because n^2 is an upper bound to n, and thus an upper bound to whatever you were considering. But in CS, we tend to mean BigOh as saying it's an upper bound, but it's also the closest upper bound (in other words, we usually mean BigOmega rather than BigOh).
#10
Re: Big O notation
Posted 13 September 2012  03:54 AM
elgose, on 13 September 2012  06:48 AM, said:
That only applies up to a point though. If you can tell right away that an algorithm is, say, O(2^n), you shouldn't even bother implementing the algorithm, no matter how much simpler it is than the alternative. That's not premature optimization  it's just common sense.
Quote
Reading from and writing to the end of a list is O(1)  just like at the front. Only random access is O(n).
Note that linked lists can have significant constant overhead compared to arrays and that there are arraybased data structures that allow appending to and deleting from the front in amortized O(1) time as well, so a linked list is very often not the best choice even if you do a lot of inserting and deleting at the front.
Quote
In my experience it's usually noncomputer scientists (and inexperienced students) that misuse the term that way.
Quote
You mean BigTheta.
This post has been edited by sepp2k: 13 September 2012  03:54 AM
