Results 1 to 7 of 7
  1. #1
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default time complexity questions

    what are the time complexities in these two cases, big O notation.

    1.
    Java Code:
    int a =3;
    while (a <= n)
         a = a*a;

    2.
    Java Code:
    public void foo (int n, int m)
    {
         int i = m;
         while (i > 100)
              i = i/3;
         for (int k=i ; k>=0; k--)
         {
              for (int j=1; j<n; j*=2)
              System.out.print(k + "\t" + j);
              System.out.println();
         }
    }
    for number 1, I would guess it would have something to do with log(_3)n

    and the second one i'm just confused. although the general rule is that with two loops is O(n^2), but i'm assuming they're tricking us here...

  2. #2
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    16,571
    Rep Power
    23

    Default

    Is this a java programming question?

  3. #3
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default

    I dunno. It's part of my Intro to Computer Sciences - Java course...

  4. #4
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default

    Does anyone have an idea??

  5. #5
    Prajin's Avatar
    Prajin is offline Senior Member
    Join Date
    Jun 2010
    Location
    Ktm, Nepal
    Posts
    120
    Rep Power
    0

    Default

    Java Code:
    int a =3;
    while (a <= n)
         a = a*a;
    In 1, what is 'n'. If it is integer and initialized (say n=3), then 'a' be 9.

    Java Code:
    public void foo (int n, int m)
    {
         int i = m;
         while (i > 100)
              i = i/3;
         for (int k=i ; k>=0; k--)
         {
              for (int j=1; j<n; j*=2)
              System.out.print(k + "\t" + j);
              System.out.println();
         }
    }
    In 2, pass m=300 and n=5, see the result your self. even better, try while (i>10), have smaller loop.

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,000
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by myst View Post
    what are the time complexities in these two cases, big O notation.

    1.
    Java Code:
    int a =3;
    while (a <= n)
         a = a*a;

    2.
    Java Code:
    public void foo (int n, int m)
    {
         int i = m;
         while (i > 100)
              i = i/3;
         for (int k=i ; k>=0; k--)
         {
              for (int j=1; j<n; j*=2)
              System.out.print(k + "\t" + j);
              System.out.println();
         }
    }
    for number 1, I would guess it would have something to do with log(_3)n

    and the second one i'm just confused. although the general rule is that with two loops is O(n^2), but i'm assuming they're tricking us here...
    For 2) the inner loop executes 2log(n) times while the outer loop executes <= 100 times, so big-Oh is 100*2log(n) == O(2log(n)).

    kind regards,

    Jos

  7. #7
    Prajin's Avatar
    Prajin is offline Senior Member
    Join Date
    Jun 2010
    Location
    Ktm, Nepal
    Posts
    120
    Rep Power
    0

Similar Threads

  1. Time complexity - foor loop
    By hawaiifiver in forum New To Java
    Replies: 5
    Last Post: 02-05-2011, 04:06 PM
  2. Time Complexity Java Code?
    By Lyricid in forum New To Java
    Replies: 11
    Last Post: 12-08-2009, 04:27 PM
  3. complexity issue!!
    By deepa8400 in forum New To Java
    Replies: 4
    Last Post: 08-25-2009, 04:25 AM
  4. Replies: 2
    Last Post: 11-04-2008, 02:48 AM
  5. Singleton considered stupid, Java and complexity
    By fishtoprecords in forum Forum Lobby
    Replies: 11
    Last Post: 07-06-2008, 03:38 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •