Answer all parts of the question given below: The largest square problem takes i
ID: 3755236 • Letter: A
Question
Answer all parts of the question given below:
The largest square problem takes in an integer n and returns the largest square number k2 such that k2 n. (For k2 to be a square num ber, k must be an integer.) Answer the following questions about the largest square problem. 1. Give pseudocode for an exhaustive search algorithm that solves the largest square problem. 2. What is the worst-case time complexity of your answer to problem 1: 3. Give pseudocode for a (lgn) algorithm that solve the largest square problem.Explanation / Answer
First given an integer , the maximum and minimum value possible is 2,147,483,647 and - 2,147,483,648 inclusive.
1. input i from user
int num
while num < i then
square = num * num
if(square <= i)
num++
else
return num --;
end
end
2. Worst case time complexity is trying to find the square root that leads to almost input i. Then it is O(n) .
3. To solve in O(log n) , try to divide the middle element -> if input i is 10 then take 10/2 -> mid = 5 and perform square of it 5 * 5 = 25 which is greater than 10 hence move to left one element if it is lesser then move to right one element and perform the same. It is a binary search problem as the list is already sorted this one applies.
input i from user
// Comment- Divide the input element by 2 and assign it to num. If greater move left or else move right.
int mid = i / 2
int num = mid
boolean check = false;
while num < i then
square = num * num
if(square <= i)
// Comment - Move right
num++
check = true;
else
if(check)
return num --;
else
num -- ;
end
end
end
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.