DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 827

int count = 1 ;
while (count < n) {
count = count * 2 ;
}

int count = 15 ;
while (count < n) {
count = count * 3 ;
}

(c)

(d)

22.4

How many stars are displayed in the following code if n is 10? How many if n is 20?
Use the Big O notation to estimate the time complexity.

for ( int i = 0 ; i < n; i++) {
System.out.print( '*' );
}

for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < n; j++) {
System.out.print( '*' );
}
}

(a) (b)

for ( int k = 0 ; k < n; k++) {
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < n; j++) {
System.out.print( '*' );
}
}
}

for ( int k = 0 ; k < 10 ; k++) {
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < n; j++) {
System.out.print( '*' );
}
}
}

(d)

(c)

22.5

Use the Big O notation to estimate the time complexity of the following methods:

public static void mA( int n) {
for ( int i = 0 ; i < n; i++) {
System.out.print(Math.random());
}
}

public static void mB( int n) {
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < i; j++)
System.out.print(Math.random());
}
}

(b)

(a)

public static void mC( int [ ] m) {
for ( int i = 0 ; i < m.length; i++) {
System.out.print(m[i]);
}

public static void mD( int [] m) {
for ( int i = 0 ; i < m.length; i++) {
for ( int j = 0 ; j < i; j++)
System.out.print(m[i] * m[j]);
}
}

for ( int i = m.length - 1 ; i >= 0 ; )
{
System.out.print(m[i]);
i--;
}
}

(c)

(d)

22.6

Design an O (n) time algorithm for computing the sum of numbers from n 1 to n 2 for
( n 1 6 n 2). Can you design an O (1) for performing the same task?

22.7

2 k . Revise the algorithm for an arbitrary n
and prove that the complexity is still O (log n ).

Example 7 in Section 22.3 assumes n =