Results 1 to 4 of 4

Math Help - Find theta notation

  1. #1
    Newbie
    Joined
    May 2007
    Posts
    7

    Find theta notation

    Hello, I have another problem I need some help with.

    I need to find out the theta notation for the number of times the statement x = x + 1 is executed, assuming that n is a positive integer in both cases. Justify your answers.

    Code:
    j = n 
    while  (j >= 1) { 
        for i = 1 to 2j  
             x = x + 1
        j = floor(j/3)
    }


    I have tried with several n to see a pattern.

    Code:
    n=1   t(n)=2
    n=2   t(n)=4
    n=3   t(n)=8
    n=4   t(n)=10
    n=5   t(n)=12
    n=6   t(n)=16
    n=7   t(n)=18
    n=8   t(n)=10
    n=9   t(n)=26
    n=10   t(n)=28
    n=11   t(n)=30
    n=12   t(n)=34
    I found that f(n) = 2n + 2*floor(n/3) + 2*floor(n/9) + 2*floor(n/27) + .... and so on works. But how do I find out the theta notation from that?

    Is it this simple: n <= f(n) <= 2n
    so f(n) = theta(n) ?

    I think I need to prove it somehow tho...

    Any suggestions?

    Cheers,
    Henrik
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by cpklas View Post
    Hello, I have another problem I need some help with.

    I need to find out the theta notation for the number of times the statement x = x + 1 is executed, assuming that n is a positive integer in both cases. Justify your answers.

    j = n
    while (j >= 1) {
    .... for i = 1 to 2j
    ........ x = x + 1
    .... j = floor(j/3)
    }
    If n is a power of 3 we have the outer loop is executed ceil(log_3(n))
    times with j=1, 3, 9, .., 3^k .. 3^{log_3(n}.

    Then the inner loop is executed:

    2, 6, .. , 2*3^{log_3(n)}

    times.

    So the number of times in assignment statement inside the inner most
    loop is executed is:

    N(n) = 2*[sum_{i=1 to log_3(n)} 3^i]

    the sum is a finite geometric series, so:

    N(n) = 2*(3^{log_3(n)+1}-1)/(3-1) = 3^{log_3(n)+1}-1 = 3*n - 1.

    Now if n > 1, is not a power of 3 we have:

    N(3^{floor(log_3(n)}) < N(n) < N(3^{floor(log_3(n)+1)})

    Now:

    N(3^{floor(log_3(n))}) = 3*3^{floor(log_3(n))}-1

    ............................. >= 3*(n-1) - 1 = 3*n -4

    And:

    N(3^{floor(log_3(n)+1)}) = 3*3^{floor(log_3(n)+1)} -1 <= 3*(n+2) - 1 = 3*n +5.

    Hence:

    3*n -4 <= N(n) <= 3*n +5.

    So for n large enough (n > 4 should suffice):

    2*n <= 3*n -4 <= N(n) <= 3*n +5 <= 6*n

    2*n <= N(n) <= 6*n

    Hence N(n)=THETA(n).

    RonL
    Last edited by CaptainBlack; May 12th 2007 at 08:06 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by cpklas View Post
    Hello, I have another problem I need some help with.

    I need to find out the theta notation for the number of times the statement x = x + 1 is executed, assuming that n is a positive integer in both cases. Justify your answers.

    Code:
    j = n 
    while  (j >= 1) { 
       for i = 1 to 2j  
            x = x + 1
       j = floor(j/3)
    }
    I have tried with several n to see a pattern.

    Code:
    n=1   t(n)=2
    n=2   t(n)=4
    n=3   t(n)=8
    n=4   t(n)=10
    n=5   t(n)=12
    n=6   t(n)=16
    n=7   t(n)=18
    n=8   t(n)=10
    n=9   t(n)=26
    n=10   t(n)=28
    n=11   t(n)=30
    n=12   t(n)=34
    I found that f(n) = 2n + 2*floor(n/3) + 2*floor(n/9) + 2*floor(n/27) + .... and so on works. But how do I find out the theta notation from that?

    Is it this simple: n <= f(n) <= 2n
    so f(n) = theta(n) ?

    I think I need to prove it somehow tho...

    Any suggestions?

    Cheers,
    Henrik
    As t(12) = 34, clearly t(n) is not bounded above by 2n, at least when
    n is as small as 12.

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2007
    Posts
    7
    Thanks heaps for that! Really appreciated.

    Henrik
    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. Replies: 3
    Last Post: February 6th 2009, 04:19 PM
  3. Replies: 1
    Last Post: January 23rd 2009, 10:53 AM
  4. Theta notation
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: May 22nd 2008, 03:46 AM
  5. little oh notation and theta
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 3rd 2007, 10:30 PM

Search Tags


/mathhelpforum @mathhelpforum