time complexity questions

[myst]

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

1.

int a =3;
while (a <= n)
     a = a*a;

2.

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...

[Norm]

Is this a java programming question?

[myst]

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

[myst]

Does anyone have an idea??

[Prajin]

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.

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.

[JosAH]

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

1.

int a =3;
while (a <= n)
     a = a*a;

2.

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

[Prajin]

Good as always Josah.