Using the pseudocode conventions of the textbook, write an 0(n) algorithm to fin
ID: 3663766 • Letter: U
Question
Using the pseudocode conventions of the textbook, write an 0(n) algorithm to find and return the maximum value of an array that contains n numbers. Write a comment between each pair of lines describing what is true when the program reaches that point in your code. What is the minimum number of bits that are needed to encode an integer in the range -1000 to 1000? From -1000000 to 1000000? From - n to n, where n is a positive integer? Rank the following 12 functions by order of growth. f_1(n) = lg n f_2(n) = n^2 f_3(n) = 2^n All the functions for f_i{f_j 1,2,3} and j {1,2,3} Consider the insertion sort algorithm presented in the book. Assume that A contains n distinct numbers. If A is sorted in ascending order, determine the number of times each line is executed. Assuming that the cost of each line is c, what is the total running time? Show the result in a way similar to the top of p. 26. If A Ls sorted in descending order, determine the number of times each line is executed. Assuming that the cost of each line is c, what Ls the total running time? Show the result in a way similar to the top of p. 26.Explanation / Answer
1.
findMax(int arr[], int n)
int max = arr[0] // assuming first element is maximum
int i =1;
for i = 1 to n
if(arr[i] > max) // if current element is greater than max
max = arr[i] // then update max with current value
return max;
2. You have 1000 numbers that are negative (-1000 to -1)
You have 1 number that is zero (0)
You have 1000 numbers that are positive (1 to 1000)
So in total you need enough bits to encode 2001 unique values.
Each bit you add doubles the number of values you can encode.
2^1 = 2 values
2^2 = 4 values
2^3 = 8 values
etc.
In order to cover 2001 numbers, you would need to have 2^11 = 2048 values.
2^10 = 1024
2^11 = 2048
1024 < 2001 < 2048
Likewise, for -1,000,000 to +1,000,000 you would need to have enough bits for 2,000,001 values
2^20 = 1,048,576
2^21 = 2,097,152
1,048,576 < 2,000,001 2,097,152
In general:
2^x 2n+1
x log(2n+1) / log(2)
x = ceiling(log(2n+1) / log(2))
Answer:
For -1000 to 1000 you need a minimum of 11 bits
For -1000000 to 1000000 you need a minimum of 21 bits
For -n to n you need a minimum of ceiling(log(2n+1) / log(2)) bits
3. Order of growth: logn < n^2 < 2^n
4. If array is sorted in assending order then, this is the BEST CASE for INSERTION SORT.
It takes O(n) time. Each line will take c time to execute(only one comparision)
If array is sorted in decreasing order then it is WORST CASE of INSERTION SORT. IT takes O(n^2) time.
= c+ 2*c + 3*c + 4*c +.....+ (n-1)*c (time taken by each line will increase linearly)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.