Results 1 to 5 of 5

Math Help - Theta notation for functions

  1. #1
    Newbie
    Joined
    May 2007
    Posts
    4

    Theta notation for functions

    I got a theta notation question here as well that im kinda stuck on.

    Select a theta notation for each of the following functions, and justify your answers thoroughly.

    a) root(n) + n + 3nlogn
    b) 2 + 4 + 8 + ... + 2^n

    don't really know how to do it and my only initial guesses were a) theta(nlgn) and b) theta(2^n), theta(C^n) c > 1 or theta(C^(n+1)) C > 1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    May 2007
    Posts
    7
    Quote Originally Posted by Papakanos View Post
    I got a theta notation question here as well that im kinda stuck on.

    Select a theta notation for each of the following functions, and justify your answers thoroughly.

    a) root(n) + n + 3nlogn
    b) 2 + 4 + 8 + ... + 2^n

    don't really know how to do it and my only initial guesses were a) theta(nlgn) and b) theta(2^n), theta(C^n) c > 1 or theta(C^(n+1)) C > 1
    On b) if you use the geometric sum formula to get (2^(n+1))/(2-1) - 1 = 2^(n+1) - 2

    then

    2^(n+1) - 2 > 2^n
    2^(n+1) - 2 = lower(2^n)

    2^(n+1) - 2 < 2*2^n
    so 2^(n+1) - 2 = O(2^n)

    so it should be theta(2^n)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2007
    Posts
    4
    Quote Originally Posted by cpklas View Post
    On b) if you use the geometric sum formula to get (2^(n+1))/(2-1) - 1 = 2^(n+1) - 2

    then

    2^(n+1) - 2 > 2^n
    2^(n+1) - 2 = lower(2^n)

    2^(n+1) - 2 < 2*2^n
    so 2^(n+1) - 2 = O(2^n)

    so it should be theta(2^n)
    with that shouldn't the - 2 on the right be a - 1 hence making the others all - 1 or am i missing something?
    Although i get wat ur saying though.

    and any tips on a) ?

    cheers for the help so far
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2007
    Posts
    7
    ahh ok. a + ar^1 + ar^2 +.... ar^n + ar^n+1 = a(r^(n+1) - 1) / (r - 1) - 1.

    we get (r^(n+1) - 1) / (2 - 1) - 1 = (r^(n+1) - 1) - 1 = r^(n+1) - 2

    Hence the -2

    Henrik
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Papakanos View Post
    a) root(n) + n + 3nlogn
    for n>e:

    n log(n) > n > sqrt(n), so:

    root(n) + n + 3n log(n) < 5n log(n),

    and of course:

    3n log(n) < root(n) + n + 3n log(n)

    so:

    3n log(n) < root(n) + n + 3n log(n) < 5n log(n)

    so: root(n) + n + 3n log(n) = THETA(n log(n)

    (note assumption that log denotes log_e here)

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help~~about the theta notation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 29th 2009, 02:11 AM
  2. Theta Notation for Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 10th 2008, 01:25 AM
  3. Theta notation
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: May 22nd 2008, 03:46 AM
  4. little oh notation and theta
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 3rd 2007, 10:30 PM
  5. Find theta notation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 14th 2007, 06:56 AM

Search Tags


/mathhelpforum @mathhelpforum