The Daily WTF: Curious Perversions in Information Technology
Welcome to TDWTF Forums Sign in | Join | Help
in Search

Rewrite an O(n log n) (or better) algorithm to be O(n^2) (or worse)

Last post 01-09-2013 5:03 PM by NeilRashbrook. 5 replies.
Page 1 of 1 (6 items)
Sort Posts: Previous Next
  • 09-27-2012 3:00 PM

    • Ben L.
    • Top 10 Contributor
    • Joined on 12-22-2010
    • Inventor of the 186-hour work week
    • Posts 3,607

    Rewrite an O(n log n) (or better) algorithm to be O(n^2) (or worse)

    Pick your favorite algorithm

    For example, with a linked list, clearing the list is quite simple (and O(1)):

    • Set the pointer to the first element to null.

    However, someone I know managed to write it in O(n^2):

    • While the list's number of elements is greater than zero.
      • Find the value of the last element in the list.
      • Remove that value from the list.
  • Morbs is the smartest!
  • 09-27-2012 10:48 PM In reply to

    Re: Rewrite an O(n log n) (or better) algorithm to be O(n^2) (or worse)

    How's that leak going tonight?
  • 09-30-2012 10:34 AM In reply to

    • TGV
    • Top 75 Contributor
    • Joined on 10-09-2005
    • Posts 705

    Re: Rewrite an O(n log n) (or better) algorithm to be O(n^2) (or worse)

    Ben L.:
    However, someone I know managed to write it in O(n^2):
     

    Extra bonus points if he then stores the discarded elements in another list, sorts them, and never uses them anymore. 'Cause that's how we keep selling faster processors and memory.

  • 11-02-2012 5:10 AM In reply to

    Re: Rewrite an O(n log n) (or better) algorithm to be O(n^2) (or worse)

     Of course, there has been extensive research on this important topic: Pessimal Algorithms and Simplexity Analysis

  • 11-28-2012 11:27 PM In reply to

    Re: Rewrite an O(n log n) (or better) algorithm to be O(n^2) (or worse)

    Locked Reply Contact

    OK, my favorite function is F(x) = 1. That's O(1). How on earth could I make it O(N^2)?? Hmmm... <Furrows eyebrow>

    G(x) = 
      For 1 .. x:
        For 1 .. x:
          NOP
    
      return F(x)
    

    What a fun and interesting challenge! Please keep posting more creative challenges!

  • 01-09-2013 5:03 PM In reply to

    Re: Rewrite an O(n log n) (or better) algorithm to be O(n^2) (or worse)

     How do you expect us to beat the recursive whitespace removal algorithm featured on CodeSOD?

Page 1 of 1 (6 items)
Powered by Community Server (Non-Commercial Edition), by Telligent Systems