3. Determine the best bound for the following code's running time using Big-O notation: [2 ...

Transcribed Image Text:

3. Determine the best bound for the following code's running time using Big-O notation: [2 × 5] i) for (i=0; i<n•n; i++){ if (i% n = 0) for(j=0; j<i; j++) printf("*"); 3 4 = } ii) 1 for (i= n; i>0; i= i/2) { for (j=1; j<i; j++) printf("*"); } 3. An array A of 2n integers has n + 1 identical numbers. How many comparisons are required to determine which number is repeated n + 1 times? [10] 5. A little boy counts from 1 to 1000 using the fingers of her left hand as follows. He starts by calling her thumb 1, the first finger 2, middle finger 3, ring finger 4, and little finger 5. Then he reverses direction, calling the ring finger 6, middle finger 7, the first finger 8, and her thumb 9, after which she calls her first finger 10, and so on. If he continues to count in this manner, on which finger will he stop? For example, to count 15, the boy will stop at middle the finger. . [10] Act 3. Determine the best bound for the following code's running time using Big-O notation: [2 × 5] i) for (i=0; i<n•n; i++){ if (i% n = 0) for(j=0; j<i; j++) printf("*"); 3 4 = } ii) 1 for (i= n; i>0; i= i/2) { for (j=1; j<i; j++) printf("*"); } 3. An array A of 2n integers has n + 1 identical numbers. How many comparisons are required to determine which number is repeated n + 1 times? [10] 5. A little boy counts from 1 to 1000 using the fingers of her left hand as follows. He starts by calling her thumb 1, the first finger 2, middle finger 3, ring finger 4, and little finger 5. Then he reverses direction, calling the ring finger 6, middle finger 7, the first finger 8, and her thumb 9, after which she calls her first finger 10, and so on. If he continues to count in this manner, on which finger will he stop? For example, to count 15, the boy will stop at middle the finger. . [10] Act