TheDon1

========(not related to question)=======
Hi, im new to this forum!
my course (carnegie technology education) requires i learn asymoptic
analysis. Which means i have to learn big-oh notation.
I think i have the idea, but, im just not exactly sure.
If i dont please tell me!
and if you would like to aid my current understanding PLZ! feel free!
==============================

========(my understanding)=========
Big-Oh notation ( O(something) ), is used to summarise
the "dominant reason for increases in running time, in an algorithm"

To use Big-Oh notation, u identify the most dominanantly expanding
part of a function, and use that within the O notation.

Big-Oh analysis (mainly in terms of sorting and searching algorithms)
is mainly concerned with the variable N (the size of the input being sorted
or searched). U use big-Oh notation to describe the effect the particular
size of N will have on the expansion of the algorithms running time.

so, for example, (im scared of being wrong here!)

void function(vector<int>& g) {

for (int a = 0; a < g.size(); a++) {
for (int z = 0; z <g.size(); z++) {
//constant body
}
}
}
N == the size of the input (as all the text books say!!)

according to my understanding, the most dominant reason for an expansion
in this functions running time is the second for loop. this is because
its amount of iterations is governed by the input (g.size()) and it is controled by its
parent loop, which is also governed by the input.
so, using big-oh notation, this function would be considered O(n^2),
or a quadratic algorithm, because:
for each parent loop of 1N (1 piece of the input (g.size()), the child loop will have to iterate N times as well, so the amount of overall iterations, mainly caused by
the child for loop (identified as the most dominant), will be n^2.
as apposed to, for example, a linear algorithm of O(n).

==========(question)=========
Am i on the right track?
is this all i need to know?
is Big-Oh ONLY used for WORST-CASE complexity, and the other ways of calculating, (listed below), for NON-WORST CASE complexity?
what is all this hear about Big-Omega/little-O,Big-theta, do i have to learn them
to understand everything?

please give me some tips and points!
thankyou very much for reading this!
TheDon1!

Mjordan2nd

Well, I appologize, as I can't answer your question, but I would like to welcome you to the forum. Hope you like it.

__________________
&quot;Every gun that is made, every warship launched, every rocket signifies, in the final sense, a theft from those who hunger and are not fed, from those who are cold and are not clothed. The world in arms is not spending money alone. It is spending the sweat of its laborers, the genius of its scientists, the hopes of its children.&quot; - Dwight D. Eisenhower

TheDon1

yo, thx for the post, i plan to regulate alot here if i remember, i wanna join some sort of programming community!, ive only been programming for about 6-7 months, but i think im ok. Ofcourse, i cant bring much to the table when it comes to assisting advanced cases, however, i plan to take what is already on the table, learn it well, pioneer my own understanding, and then bring it back to the table!!

the table!

haha!

peace for the post!

Berto

I think you are on teh right track cant say 100% though.

inner loop has to run through N*N iterations (eg if size = 10 then obviously inner loop runs 10 times, for each outer loop so 10 * 10 which is 10^2)

So yeah it is N^2, not to sure about the O thing though, never seen it at my uni.

__________________
"Put your hand on a hot stove for a minute, and it seems like an hour. Sit with a pretty girl for an hour, and it seems like a minute. THAT'S relativity."

- Albert Einstein

Pizentios

heh, i've never even heard of Big OH.

welcome to the forums dude.

__________________
Profanity is the one language that all programmers understand.

Check out my Blog <---updated Nov 30 2007!

Ooble

Welcome to the place. And sorry, but I've never heard of Big OH.

__________________
Me :: You :: Them

Xyler

Hi.

I am also new to the forums but you are on the right track. Did it earlier this year and you have the basic idea. Can check up on some stuff if you need to know more.

The stuff that runs in the loop will change the initial value of big oh, but using some rules you should get you eventually refine it to O(n^2). EG if there were three instructions in the loop would be O((n^2)*3). Can't remember the difference between small and big omega right now.

Anyways good luck

__________________
Be vewwy vewwy quiet. I'm hunting wuntime ewwors.

kurifu

Very basic way to look at that... graph you O(...) notation in 2D cartesian space. (just the ... part). When analyzing a search function the X-axis pretty much represents the number of elements in which you are searching (or sorting) and the Y element is the number of high-level operations that will be required to complete the search.

Remember that it is only high level operations here that count since constants (which would represent your low level operations) really have no importance in big Oh notation. The lower order your convergence, typically the better an algorithm you have (though it will converge to 0 slower). While larger order notations (such as O(n^2)) will require more operations to complete but mathematically will converge to 0 faster.

__________________
Clifford Matthew Roche &lt;geek@cliffordroche.com&gt;
Web Hosting: http://www.crd-hosting.com
Consulting: http://www.crdev-consulting.com

TheDon1

Yo hi dudes, thx to all of u for welcoming me, in the holidays i will most surely try hard to contribute to these forums!

do u dudes know any "mathematically unburdoning" site that explains Big-Oh?

however, what i am looking for now, are good ways to figure out the Big-Oh
notation, when loops have complicated incrementation of decrementation.

like, in my first post in this thread, my loops incremented by 1, with the pure beauty of the ++ operator, however, there are some algorithms that have stuff like:

(shell sort (sorting))
N = number of objects in the collection that is to be sorted
3 loops:
1st loop, loop variable i = N/2, update: i / 2
2nd loop, loop varibale z = i, update: z++
3rd loop, loop varibale x = i, update: x -= i;

this is good example of having an algorithm that is not so easy ( for me ), to work out its Big-Oh running time.

does anyone have any tips?, do u know any where that they have a DIRECT means for calculating big-oh notation based on loop / loop updates?


dudes thx for reading again, peace!

Ashcroft

A site that covers the basic math of Big-O is http://mathworld.wolfram.com/AsymptoticNotation.html

Some of the most common algorithms you have to deal with are O(1) - retrieval from a perfect hash, O(log2 N) - binary search, O(N) - linear search, O(N log2 N) - quicksort, and O(N^2) - insertion sort. The last should only be used for very small N, and anything worse is most likely unsuitable for any real world programming outside of very specialized applications.

The easiest way I've found to estimate the big-oh of an algorithm is to factor out the operations of each loop, discard any operations that tend toward 0 and multiply the operations together. Even though some O(N^2) algorithms are going to be faster in practice than another O(N^2) algorithm it really doesn't matter much at that level of abstraction - after all we are talking about a level of abstraction where 1 and 1000 are looked at as being the same because they are both constant factors unrelated to input size.