Thread: HELP!!! Big-O of my anagram program

  1. #1
    Registered User
    Join Date
    Sep 2001
    Posts
    14

    HELP!!! Big-O of my anagram program

    This is probably a very stupid question. I made a working program that reads in a word list and spits out all the anagram classes in the word list in alphabetical order. For example, if the program read in the list:

    car
    dog
    bed
    stop
    god
    pots
    arc
    tops

    the program will output:

    arc car
    bed
    dog god
    pots stop tops

    If you're familiar with coding anagram programs, I used two sorts:

    - Quicksort to sort out the individual words. The original and the sorted words are stored in each node of the link list.
    - Mergesort to sort out the linked list.

    My questions are, what would be the Big-O running time of my program if the input word list have N words and L is the maximum length of any word? (would it be NlogN+LlogL since the two sorts have a Big-O of nlogn?)

    Also, what would be the Big-O if the input list contains only two words?

  2. #2
    Duck-billed Platypus
    Guest

    Cool

    I'm not familiar with anagram programming, but it seems that the growth rate would be NlogN. It wouldnt be NlogN + LlogL becuase when you determine the growth rate of a function, you only count the fastest growing term. Growth rate is similar to the degree of a polynomial, the degree just determines how fast the values will grow. Since the polynomial

    x^4 + x^3 + x^2 + x

    has a degree of 4, it follows that the growth rate of a function would be determined by the fastest growing portion of your algorithm.

  3. #3
    Linguistic Engineer... doubleanti's Avatar
    Join Date
    Aug 2001
    Location
    CA
    Posts
    2,459
    >x^4 + x^3 + x^2 + x

    yes, monomials of higher terms make those of lower terms negligible in their scale, regardless of whether they are exponential or logarithmic...
    hasafraggin shizigishin oppashigger...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM
  2. Anagram program
    By cdonlan in forum C++ Programming
    Replies: 4
    Last Post: 04-18-2005, 12:04 PM
  3. First (semi) usefull program. Big accomplishment for me.
    By imortal in forum C++ Programming
    Replies: 1
    Last Post: 05-03-2003, 12:07 PM
  4. My First BIG program done!!! Check it out!!
    By biosninja in forum C++ Programming
    Replies: 8
    Last Post: 09-04-2002, 03:33 PM
  5. Replies: 2
    Last Post: 05-10-2002, 04:16 PM