Thread: Heeeelp.. Question...

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    249

    Question Heeeelp.. Question...

    Please give me some ideas about this question....

    Suppose by carful measurement we have discovered a function that describes the precise running time of some algorithm. For each of teh following such functions, discribe the algorithmic running time in big-Oh notation:

    A. 3n2 + 3n + 7
    B. (5*n) * (3 + log n)
    C. (5n+4)/ 6
    D. 1+2+3+ ..... +n
    E. n + log n2
    F. (n+1) log n / 2

    Please help me ...
    Thank you...
    C++
    The best

  2. #2
    Registered User matheo917's Avatar
    Join Date
    Sep 2001
    Posts
    279
    hmmm....

    homework...........?

  3. #3
    Registered User
    Join Date
    Apr 2002
    Posts
    249

    Yes it is ....

    But I need some hints not all.

    becuase I couldn't understand the question ....

    that is all
    ...
    C++
    The best

  4. #4
    Still A Registered User DISGUISED's Avatar
    Join Date
    Aug 2001
    Posts
    499
    Maybe this will help.

    Quadratic Time

    If the largest term in a formula is no more than a constant times n^2, then the algorithm is said to be big-O of n^2..written O(n^2)
    Example: n^2+7n

    Linear Time

    If the largest term in a formula is a constant times n, then the algorithm is said to be big-O of n....written O(n)
    Example: 50n+5

    Logarithmic Time

    If the largest term in a formula is a constant times a logarithm of n, then the algorithm is big-O of the logarithm of n..written
    O(log n)

    From Data Structures and Other Objects Using C++, Michael Main, Walter Savitch

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Each expression describes the maximum possible running time for an algorithm.
    >A. 3n2 + 3n + 7
    Let's forget about this for a second and work on how to determine O notation. Given the following algorithm:
    Code:
    for ( i = 0; i < N; i++ ) {
        for ( j = 0; j < N; j++ ) {
            // Stuff
        }
    }
    for ( k = 0; k < N; k++ ) {
        // Stuff
    }
    The first set of nested loops is O(N2) and the second loop is O(N). This is O(max(N2,N)) which is O(N2). Remember that O notation ignores constants and low order terms because they don't matter when the algorithm becomes very large. So once you strip the non-essentials, O notation is very easy to determine.

    -Prelude
    My best code is written with the delete key.

  6. #6
    Registered User
    Join Date
    Apr 2002
    Posts
    249

    Thanks Guys...

    I think that should do it ...

    Thank you for your help....
    I am going home right now ...
    I will chick it there ...
    Thanks
    C++
    The best

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  2. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  3. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  4. Question about linked lists.
    By cheeisme123 in forum C++ Programming
    Replies: 6
    Last Post: 02-25-2003, 01:36 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 01:47 AM