Consider the following procedure. pre: n is a positive integer pre: v[1..n] is a binary vector...

Transcribed Image Text:

Consider the following procedure. pre: n is a positive integer pre: v[1..n] is a binary vector of length n, i.e., each entry is either 0 or 1 foo (v, n) 1. 2. 3 4 5. 6. 7. i = 1; while i<n and v[i]=0 do i = 1+1 od; for j from 1 to i do print ("Hello world!") od; a) How many inputs are there are of size n? b) What is the worst case number of calls to print? Give an exact formula in terms of n and justify your answer by giving an example of a worst case input of size n. c) For i {1, 2,..., n}, let S, denote the subset of inputs of size n for which the number of calls to print is i. Describe what an element of S; looks like, and derive an expression for S, the number of elements of S₁. Act d) What is the average case number of calls to print? Derive an exact closed form formula Go in terms of n. Consider the following procedure. pre: n is a positive integer pre: v[1..n] is a binary vector of length n, i.e., each entry is either 0 or 1 foo (v, n) 1. 2. 3 4 5. 6. 7. i = 1; while i<n and v[i]=0 do i = 1+1 od; for j from 1 to i do print ("Hello world!") od; a) How many inputs are there are of size n? b) What is the worst case number of calls to print? Give an exact formula in terms of n and justify your answer by giving an example of a worst case input of size n. c) For i {1, 2,..., n}, let S, denote the subset of inputs of size n for which the number of calls to print is i. Describe what an element of S; looks like, and derive an expression for S, the number of elements of S₁. Act d) What is the average case number of calls to print? Derive an exact closed form formula Go in terms of n.

Answer rating: 100% (QA)

Lets answer each part of the question step by step considering the function foovn defined where v is an binary vector of length n and n is a positive ... View the full answer