ITEC103 Introduction to Software Design Time Complexity and Recursion

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit


ITEC103 Introduction to Software Design

Module Exam

Time Complexity and Recursion

QUESTION SET 2


Instructions

。Write your answer neatly in space provided after each question, request blank pages if you need more space.

Answers must be clear enough to read in order to be marked

。  Any attempt of plagiarizing will result in an automatic zero.



Questions

Question 1 (20 points)

Consider the method foo,

int foo (int a) {

if (a == 1) {

return 0;

}

return 2 + foo (a / 2) ;

}

(a)  (10 points)  What is the value of result when the following code is executed? Show your working.

int result = foo (18) ;

(b)  (10 points)  What kind of values, if passed to the method foo, will result in the method calling itself indefi- nitely?



Question 2 (30 points)

Write a recursive method that when passed an integer n, returns the product of all positive integers up n. You can assume that n > 1. For example, if you pass 4, the method returns 24 (1 * 2 * 3 * 4)


Question 3 (10 points)

If an o(n * n) algorithm takes 5 units of time to process 12 items, how much time will it take approximately to process 48 items?


Question 4 (10 points)

Write a piece of code that has o(n) complexity


Question 5 (15 points)

Match the codes with correct complexities

for(int i=1; i < n; i++);

for(int i=1; i < n; i*=2);

for(int i=1; i <= n; i+=n);

for(int i=1; i < n*n; i/=2);

o(log2 (n)2 )

o(1)

o(log2 (n))

o(n)


Question 6 (15 points)

Write a recursive method containsUpperCases that when passed a String object, returns true if the String contains any uppercase letters of the English alphabet, and false otherwise. Return false if the String is null or empty.














2022-02-09