The Big O

This is a discussion on The Big O within the Tech Board forums, part of the Community Boards category; Question on the Big-O runtime efficiency Need some help with these problems Assume T(n) is a count of the number ...

  1. #1
    Registered User
    Join Date
    Aug 2005
    Posts
    15

    The Big O

    Question on the Big-O runtime efficiency
    Need some help with these problems


    Assume T(n) is a count of the number of key operations for an algorithm that processes a list of n elements. Determine the Big-O runtime efficiency of the algorithm.

    T(n) = O(1) is there an answer for this?? nothing to solve?

    T(n) = O(n) is there an answer for this?? nothing to solve?

    Indicate the running time of each algorithm or code segment.

    Outputting the first and last letter in a string: (i) O(n2), (ii) O(n), (iii) O(1), (iv) O(log2 n)?

    Determining the number of tokens (blocks of nonwhitespace characters) in a string: (i) O(n2), (ii) O(n), (iii) O(1), (iv) O(log2 n) ?
    Last edited by newbiec++; 01-10-2006 at 09:37 PM. Reason: added information

  2. #2
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    This would depend on what the definition of 'string' is.

    [edit]Oh, and what do you expect as a response? You haven't explained what you don't understand.

  3. #3
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    Code:
    This would depend on what the definition of 'string' is.
    I was thinking the same thing, but I couldn't think of a clever enough way to say it. There are at least 3 different types of strings I can think of: std::string, c style strings, and length prefixed strings. I bet his professor was talking about std::string, so the answer is O(1). I can't wait for someone to scream, "That's not true--it's implementation dependent!"
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  4. #4
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    I thought this thread was about something totally different based on the title, but I guess that discussion would be reserved for another forum.


Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How Big is Too Big
    By kpreston in forum C Programming
    Replies: 4
    Last Post: 10-25-2008, 10:16 AM
  2. RSA: Do I need to use a big int package for this?
    By MrSteve in forum C Programming
    Replies: 3
    Last Post: 04-27-2008, 06:05 AM
  3. Big and little endian
    By Cactus_Hugger in forum C Programming
    Replies: 4
    Last Post: 10-12-2005, 07:07 PM
  4. determining big o, theta, omega?
    By ced2140 in forum C Programming
    Replies: 1
    Last Post: 12-06-2004, 12:21 AM
  5. Looking for some big C/C++ projects
    By C-Dumbie in forum C Programming
    Replies: 5
    Last Post: 09-16-2002, 12:18 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21