Thread: linear, quadratic and cubic algorithms

having just worked out the meaning behind what a cubic and quadratic algorithm is can anyone provide examples of these in code? I mostly know Java, and one example I know is nested 'for loops' where in quadratic form the structure would be a single for with a nested for and cubic being a for loop with a nested for and further nested for (phew...)......

would say a while loop with a for loop inside be considered quadratic? How about nested methods where a for loop calls another method which contains another for loop?

To speak about cubic, quadratic etc. you have to define a function of what argument you are going to use.

For example, complexity of graph algorithms is often dependent from both number of vertices and edges in the graph.

If you are interested in just examples of code consider searching for sorting algorithms. Bubble soft and insertion sort are quadratic. Merge sort and quick sort are n log n. Bucket sort is linear, but needs additional memory. You can find code for these algorithms in Wikipedia.

Originally Posted by BlasW

To speak about cubic, quadratic etc. you have to define a function of what argument you are going to use.

For example, complexity of graph algorithms is often dependent from both number of vertices and edges in the graph.

If you are interested in just examples of code consider searching for sorting algorithms. Bubble soft and insertion sort are quadratic. Merge sort and quick sort are n log n. Bucket sort is linear, but needs additional memory. You can find code for these algorithms in Wikipedia.

thanks....its a good idea to look at the sorting algorithms for guidance I will do that.....

.....one thing I was wondering though was if nested methods of other such code structures can effectively act like cubic or quadratic formulas and therefore degrade overall program performance when I would have been attempting to construct a linear O(n) or nlogn structure....?

Any recursive code can be rewritten as non-recursive (at least by rough emulation of the stack).

Resource consumption by recursion (in conventional programming languages at least) is not related to O-complexity (in general case).