1. Member Join Date
May 2010
Posts
44
Rep Power
0

## 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...  Reply With Quote

2. ## Is this a java programming question?  Reply With Quote

3. Member Join Date
May 2010
Posts
44
Rep Power
0

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

4. Member Join Date
May 2010
Posts
44
Rep Power
0

## Does anyone have an idea??  Reply With Quote

5. ## 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.  Reply With Quote

6. ##  Originally Posted by myst 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  Reply With Quote

7. ## Good as always Josah.  Reply With Quote

#### Posting Permissions

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