# time complexity questions

• 07-12-2010, 10:53 PM
myst
time complexity questions
what are the time complexities in these two cases, big O notation.

1.
Code:

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

2.
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...
• 07-12-2010, 11:09 PM
Norm
Is this a java programming question?
• 07-12-2010, 11:21 PM
myst
I dunno. It's part of my Intro to Computer Sciences - Java course...
• 07-13-2010, 07:11 AM
myst
Does anyone have an idea??
• 07-13-2010, 08:17 AM
Prajin
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.

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.
• 07-13-2010, 09:15 AM
JosAH
Quote:

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

1.
Code:

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

2.
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
• 07-13-2010, 12:02 PM
Prajin
Good as always Josah.