Notices
Results 1 to 4 of 4

Thread: linear, quadratic and cubic algorithms

  1. #1 linear, quadratic and cubic algorithms 
    Forum Bachelors Degree
    Join Date
    Jul 2009
    Posts
    404
    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?


    Reply With Quote  
     

  2.  
     

  3. #2 Function of what? 
    Forum Freshman
    Join Date
    Oct 2010
    Posts
    98
    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.


    Reply With Quote  
     

  4. #3  
    Forum Bachelors Degree
    Join Date
    Jul 2009
    Posts
    404
    Quote Originally Posted by BlasW View Post
    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....?
    Reply With Quote  
     

  5. #4  
    Forum Freshman
    Join Date
    Oct 2010
    Posts
    98
    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).
    Reply With Quote  
     

Similar Threads

  1. linear, quadratic and cubic equations
    By fatman57 in forum Mathematics
    Replies: 4
    Last Post: June 3rd, 2012, 07:55 AM
  2. (quadratic) convergence
    By logic in forum Mathematics
    Replies: 0
    Last Post: April 27th, 2012, 12:27 AM
  3. cubic equation
    By Supercuriositine in forum Mathematics
    Replies: 7
    Last Post: November 1st, 2009, 12:04 AM
  4. Replies: 5
    Last Post: July 19th, 2009, 05:42 PM
  5. Quadratic Equations
    By NurBoEFZZJ in forum Mathematics
    Replies: 2
    Last Post: April 15th, 2008, 03:39 AM
Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •