## Question-62

Question-62

Give a big-O estimate for each of the following function. For the function g in the estimate f (x) is O (g(x)) , use a simple function g of smallest order.

a)

g (n) = ?

b)

g(n) = ?

c)

g(n) = ?

Solution

a)

b)

c)

## Question-61

Question-61

Let k be a positive integer. Which of the following mathematical equations correctly shows that

1k + 2k + ………….  + nk  is O ?

Solution

## Question-60

Question-60

To establish a big-O relationship, find witnesses C and k such that

whenever x > k.

Find the least integer n such that f (x) is  O  for each of the functions.

a)  f(x) = log x

n = ?

b)  f (x) = 4

n = ?

c)  f (x) =

n = ?

d)  f (x) =

n = ?

Solution

a) 8

b) 7

c) 0

d) -1

## Question-59

Question-59

To establish a big-O relationship, find witnesses C and k such that

whenever x > k.

Determine whether each of these functions is O

a) f (x) = 11x + 11

b) f (x) = + 700

c) f (x) = x log x

d) f (x) =

e) f (x) =

f) f (x) =

Solution

a) Yes

b) Yes

c) Yes

d) No

e) No

f) Yes

## Question-58

Question-58

What of the following is an algorithm that locates the first occurrence of the largest element in a finite list of integers? The integers in the list are not necessarily distinct.

Solution

procedure first largest ( a1 , a2 , ……… , an : integers)

max = a1

location = 1

for  i = 2 to n

if max < ai then

max = ai

location = i

return location

## Question-57

Question-57

Consider an algorithm that used only assignment statements that replaces the quadruple (w, x, y, z) with (x, y, z, w). What is the minimum number of assignment statements needed?

Solution

5 assignment statements

## Question-56

Question-56

Which statement best describes an algorithm that takes as input a list of  n  integers and produces as output the smallest difference obtained by subtracting an integer in the list from the one following it

Solution

Set the answer to be . For  i going from 1 through   n – 1 , complete the value of the ( i + 1)st  element in the list minus the ith element in the list. If this is smaller then the answer, reset the answer to be this value.

## Question-55

Question-55

Which of the following algorithms can be used to find the sum of all the integers   in a list?

Solution

Procedure AddUp (a1,……….. , an : integers)

sum = a1

for i = 2 to n

sum = sum + ai

return sum

## Question-54

Question-54

Determine which characteristics of an algorithm described in the text (after Algorithm 1) the following procedures have and which they lack. Select characteristics that the procedures have and leave characteristics unselected that the procedures lack.

a) procedure double (n : positive integer

while  n > 0

n  – 10n

b)  procedure divide  ( n : positive integer)

while  n   0

m =

n = n – 1

c)  procedure sum  ( n : positive interger)

sum = 0

while i < 7

sum = sum + i

d) procedure chose ( a , b : integers)

x = either a or b

Solution

a)

Input

Output

Definiteness

Correctness

Effectiveness

Generality

b)

Input

Output

Definiteness

Correctness

Finiteness

Generality

c)

Input

Output

Correctness

Finiteness

Effectiveness

Generality

d)

Input

Output

Correctness

Finiteness

Effectiveness

Generality

## Question-53

Question -53

List all the steps used by Algorithm 1 to find the maximum of the list

5, 9, 13, 9, 11, 2, 16, 2, 14, 4

Solution

max = 5 ,  i = 2 ,

max = 9 , i = 3 ,

max = 13 , i = 4 , i = 5 , i = 6 , i = 7 ,

max = 16 , i = 8 , i = 9 , i= 10 , i = 11