'BigOh' Notation

[DansTransAM]

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

[WingedPanther]

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.

[Lop]

What are you guys talking about? I've never even heard of Oh notation.

[WingedPanther]

"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.