Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
In my data structures class we have been looking at certain Java code and determining how effecient the algorithm/code is.
Our teacher wants to able to look at code (for loops, if statements, etc) and be able to come to up with O notation of the algorithm. I have been having trouble identifying the BigOh number in general.
Any tips on looking at code? Nested loops?
Thanks
'BigOh' Notation
Started by
Guest_DansTransAM_*
, Sep 08 2006 12:50 PM
3 replies to this topic
Back to top|
|
|
#2
Posted 13 September 2006 - 08:08 PM
WingedPanther
-
- Moderators
-
- 16,831 posts
A spammer's worst nightmare
No loops = O(1).
one loop = O(n).
two loops = up to O(n^2).
three loops = up to O(n^3).
Recursion = who the heck knows??? could be O(ln(ln(n))) or O(n!)
O is not trivial to determine for many realistic cases.
one loop = O(n).
two loops = up to O(n^2).
three loops = up to O(n^3).
Recursion = who the heck knows??? could be O(ln(ln(n))) or O(n!)
O is not trivial to determine for many realistic cases.
#3
Posted 14 September 2006 - 07:44 AM
Lop
-
- Members
-
- 1,172 posts
Speaks fluent binary
What are you guys talking about? I've never even heard of Oh notation.
#4
Posted 14 September 2006 - 08:56 AM
WingedPanther
-
- Moderators
-
- 16,831 posts
A spammer's worst nightmare
"Big-O" notation is a way to characterize functions. The definition is:
f(x) is in O(g(x)) if k*g(x) > f(x) for all x >N, and some constants k.
There are two aspects of a program that are usually measured with Big-O notation: memory usage and processing time (steps used). For a a given program, suppose that m(x) is the memory usage, and p(x) is the processing time, based on an input x.
If m(x) is O(1), then it used a fixed amount of memory, regardless of x.
If m(x) is O(x), then it is linearly related to x, or fixed. If m(x) is O(1), it is also O(x).
If m(x) is O(x^2), then it is quadraticly related to x. Obviously, the larger the function, the more of a memory hog our program is.
Similar analysis can be applied to p(x). It's usually not too hard to get m(x) with a low Big-O, but p(x) can be more of an issue. Sorting is a classic problem, which is easy to code in O(x^2), but cannot be gotten down to O(x). This means processing time MUST grow faster than the number of items being sorted. I wrote a program a while back that I estimated to be O(((x!)!)!). Needless to say, it became an issue to run it on any kind of useful data.
f(x) is in O(g(x)) if k*g(x) > f(x) for all x >N, and some constants k.
There are two aspects of a program that are usually measured with Big-O notation: memory usage and processing time (steps used). For a a given program, suppose that m(x) is the memory usage, and p(x) is the processing time, based on an input x.
If m(x) is O(1), then it used a fixed amount of memory, regardless of x.
If m(x) is O(x), then it is linearly related to x, or fixed. If m(x) is O(1), it is also O(x).
If m(x) is O(x^2), then it is quadraticly related to x. Obviously, the larger the function, the more of a memory hog our program is.
Similar analysis can be applied to p(x). It's usually not too hard to get m(x) with a low Big-O, but p(x) can be more of an issue. Sorting is a classic problem, which is easy to code in O(x^2), but cannot be gotten down to O(x). This means processing time MUST grow faster than the number of items being sorted. I wrote a program a while back that I estimated to be O(((x!)!)!). Needless to say, it became an issue to run it on any kind of useful data.
