Comparison of running times

This is a discussion on Comparison of running times within the C++ Programming forums, part of the General Programming Boards category; Could one of ya'll wise programmers out there be able to tell me what this question is asking me? I ...

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    Comparison of running times

    Could one of ya'll wise programmers out there be able to tell me what this question is asking me? I couldn't figure it out and this is for my Data Structures course that I am taking:
    'For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algortihm to solve the problem takes f(n) microseconds.'

    ------|1 second|-----|1 minute|-----|1 hour|-----|1 day|----
    lg n
    ------|--------|------|--------|-----|------|-----|-----|----
    sqrt(n)
    ------|--------|------|--------|-----|------|-----|-----|----
    n
    ------|--------|------|--------|-----|------|-----|-----|----
    n lg n
    ------|--------|------|--------|-----|------|-----|-----|----
    n^2
    ------|--------|------|--------|-----|------|-----|-----|----
    n^3
    ------|--------|------|--------|-----|------|-----|-----|----
    2^n
    ------|--------|------|--------|-----|------|-----|-----|----
    n!
    ------|--------|------|--------|-----|------|-----|-----|----

    Again, I do not require the answer I just need to know what this question is asking me. Thanks a lot folks.

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Some of these you can solve for n.
    For example
    sqrt(n) = 3600.
    Solving this for n gives the value of n for the algorithm
    to take 1 hour.

    Others such as the factorial, n lg n you have
    to use a calculator or just write a quick program to
    calculate it.

  3. #3
    Registered User
    Join Date
    Aug 2001
    Posts
    244

    Re: Comparison of running times

    Originally posted by supaben34
    Could one of ya'll wise programmers out there be able to tell me what this question is asking me? I couldn't figure it out and this is for my Data Structures course that I am taking:
    'For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algortihm to solve the problem takes f(n) microseconds.'

    ------|1 second|-----|1 minute|-----|1 hour|-----|1 day|----
    lg n
    ------|--------|------|--------|-----|------|-----|-----|----
    sqrt(n)
    ------|--------|------|--------|-----|------|-----|-----|----
    n
    ------|--------|------|--------|-----|------|-----|-----|----
    n lg n
    ------|--------|------|--------|-----|------|-----|-----|----
    n^2
    ------|--------|------|--------|-----|------|-----|-----|----
    n^3
    ------|--------|------|--------|-----|------|-----|-----|----
    2^n
    ------|--------|------|--------|-----|------|-----|-----|----
    n!
    ------|--------|------|--------|-----|------|-----|-----|----

    Again, I do not require the answer I just need to know what this question is asking me. Thanks a lot folks.
    It's asking to use each function as a way of calculating how large of a problem, n, can be calculated in t seconds.

    f(n) = t

    so sqrt(n) = 100 microseconds (or I think 100 microseconds is 1 second)

    you'd have to solve by squaring both sides, so

    n = 10000

    which means using sqrt, a problem of size 10000 could be solved in 1 second.

    Hope that makes sense!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Replies: 13
    Last Post: 12-09-2008, 10:09 AM
  3. Monitor a running instance of MS Word
    By BobS0327 in forum C# Programming
    Replies: 0
    Last Post: 07-18-2008, 12:40 PM
  4. how can I re-sort a map
    By indigo0086 in forum C++ Programming
    Replies: 8
    Last Post: 06-01-2006, 06:21 AM
  5. Fastest STL container?
    By Shakti in forum C++ Programming
    Replies: 18
    Last Post: 02-17-2006, 01:07 AM

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