Click here for answers 

For each of the following sequences of code, use O() notation to describe the
running time in terms of N. Give a lower bound for the running time, don't
just answer that all are O(2^n)

1.  for (int j = 1; j <= N; j++) {
	int k = 1;
	while (k < j) {
	    k = k * 2;
	}
	cout << j << " " << k << endl;
    }

    (a) Running time of above fragment of code is O(__________)
    (b) Suppose the statement, k = k * 2; were replaced with k = k * 3. Will
        it change the running time ?
    (c) What do you think this code fragment does ?


2.  double avg(double m[N][N], itn r, int c) {
    	double sum = 0.0;
	for (int j = r-1; j <= r+1; j++) {
	    for (int k = c-1; k <= c+1; k++) {
	        sum = sum + m[j][k];
	    }
	}

	return sum/9.0
    }

    double puzzle[N][N];
    ....
    for (int r = 1; r < N-1; r++) {
        for (int c = 1; c < N-1; c++) {
	    puzzle[r][c] = avg(puzzle,r,c);
	}
    }

    (a) Running time of above fragment of code is O(__________)
    (b) Does it matter if the parameter passing mechanism is call by value
        instead of call by reference

 Click here for answers