Jaypee Institute of Information Technology (JIIT) 2007 B.Tech Computer Science and Engineering DATA STRUCTURES - Question Paper

JUIT WAKNAGHAT
Test 3
DATA STRUCTURES

1. Consider the subsequent program fragments. In every case work out f(n), the exact
number of unit-time operations performed, as a function of the input size n, then simplify
your final ans using O-notation.

(i) for (i = 1; i = n; i++)
for (j = 1; j = n-i; j++)
// Do an operation requiring unit time

(ii) for (i ??1; i for (j ??1; j for (k ??1; k ??i*j; k??)
// Do an operation requiring unit time

2. Are the subsequent statements actual or false?
(i) 2n+1 = O( 2n )
(ii) 22n = O( 2n )
(iii) log2(2n) = O( log2(n) )
(iv) loga(n) = O( logb(n) ), where a and b are positive integers

In every case provide a careful argument based on the mathematical definition of O notation.

Earning:   Approval pending.