Question

int bsearch(int[] arr, int key) { int lo = 0, mid, hi = arr.length-1; while (...

int bsearch(int[] arr, int key) {

int lo = 0, mid, hi = arr.length-1;

while ( lo <= hi ) { mid = (lo + hi) / 2;

if ( key < arr[mid] ) hi = mid – 1;

else if ( arr[mid] < key )

lo = mid + 1;

else return mid;

}

return -1; }

Count the number of operations (comparisons and assignments), find an original function with an input n, and give an analysis of the running time in terms of asymptotic complexity (Big-O). Please explain answer.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1 
int bsearch(int[] arr, int key) {               -> 1 time
    int lo = 0, mid, hi = arr.length-1;         -> 1 time
    while ( lo <= hi ) { mid = (lo + hi) / 2;   -> log(n)+1 time
        if ( key < arr[mid] ) hi = mid – 1;     -> log(n) time
        else if ( arr[mid] < key ) lo = mid + 1;    -> log(n) time
        else return mid;                            -> log(n) time
    }                                               -> log(n)+1 time
    return -1;                                   -> 1 time
}

Recursive formula for the given function is
T(n) = T(n/2) + 1
     = T(n/4) + 1 + 1
     = T(n/8) + 1 + 1 + 1
     ......
     ......
     ......
     = T(n/n) + 1 + .... + 1 + 1 + 1 [log(n) +1 terms]
     = 1 + 1 + .... + 1 + 1 + 1 [log(n) +1 terms]
     = log(n)
     = O(logn)

So, time complexity = O(logn)
0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Please find the BigO function with explanation for each of the programs below: - Recursive binary...
Please find the BigO function with explanation for each of the programs below: - Recursive binary search - Computing the factorial of N - Computing the N-th Fibonacci number. import java.util.Scanner; public class Recursive { public static void main(String args[]) { int arr[]= {7,9,12,15,28,57,92}; Scanner in = new Scanner(System.in); int key; System.out.print("Enter key to search in array : "); key = in.nextInt(); int index = binarySearch(arr,0,arr.length-1,key); if(index==-1)System.out.println(key + " is not found in array\n"); else System.out.println(key + " is found...
Restricted structures such as stack and queue are fast, but they do not support access in...
Restricted structures such as stack and queue are fast, but they do not support access in the key field mode. Group of answer choices True False Big O analysis evaluates an algorithm based on its _________ performance. Group of answer choices A. average-case B. best-case C. worst-case Which of the following algorithms is the fastest in speed? Group of answer choices A. Polynomial time algorithm B. Linear time algorithm C. Exponential time algorithm The following code gives an implementation of...
convert the while loop into for loop x = int(input('Enter initial value: ')) count = 0...
convert the while loop into for loop x = int(input('Enter initial value: ')) count = 0 if(x<1): print('Error') exit() print('Initial value is: ',x,' ',end='') while(x!=1): if(x%2==0): x=x/2 else: x=3*x+1 count+=1 if(x!=1): rint('Next value is: ',int(x),' ',end='') else: print('Final value ',int(x),', ',end='') print('number of operations performed ',int(count),' ',end='') break
#include <iostream> #include <string> using namespace std; int pal(int n, int temp) {    // Using...
#include <iostream> #include <string> using namespace std; int pal(int n, int temp) {    // Using division of 10 trick    if(n == 0)        return temp;    // Build the number backs.    temp = (temp * 10) + (n % 10);    // Then advance through the number.    return pal(n / 10, temp); } int main() {    system("clear");    int num;        // Ask the user for an input.        cout << "\nEnter...
public int linearSearch2(ArrayList<Integer> pList, Integer pKey) { for (int i = 0; i <= pList.size() /...
public int linearSearch2(ArrayList<Integer> pList, Integer pKey) { for (int i = 0; i <= pList.size() / 2; ++i) { if (pList.get(i).equals(pKey)) { return i; } else if (pList.get(pList.size() - 1 - i).equals(pKey)) { return pList.size() - 1 - i; } } return -1; } ----- Q1)Which function f(n) counts how many times the key operation(s) is(are) performed as a function of the list size n when pKey is not in pList (the worst case behavior of linearSearch2() occurs when pKey...
Code Example 8-1 1. int count = 1; 2. int item_total = 0; 3. int item...
Code Example 8-1 1. int count = 1; 2. int item_total = 0; 3. int item = 0; 4. while (count < 4) { 5.      cout << "Enter item cost: "; 6.      cin >> item; 7.      item_total += item; 8.      ++count; 9. } 10. int average_cost = round(item_total / count); 11. cout << "Total cost: " << item_total << "\nAverage cost: " << average_cost; (Refer to Code Example 8-1.) If the user enters 5, 10, and 15 at the prompts, the output is: Total...
For a C program hangman game: Create the function int setup_game [int setup_game ( Game *g,...
For a C program hangman game: Create the function int setup_game [int setup_game ( Game *g, char wordlist[][MAX_WORD_LENGTH], int numwords)] for a C program hangman game. (The existing code for other functions and the program is below, along with what the function needs to do) What int setup_game needs to do setup_game() does exactly what the name suggests. It sets up a new game of hangman. This means that it picks a random word from the supplied wordlist array and...
ex3 Write a method public static boolean isPalindrome(String input) that uses one or more stacks to...
ex3 Write a method public static boolean isPalindrome(String input) that uses one or more stacks to determine if a given string is a palindrome. [A palindrome is a string that reads the same forwards and backwards, for example ‘racecar’, ‘civic’]. Make sure that your method works correctly for special cases, if any. What is the big-O complexity of your method in terms of the list size n. Supplementary Exercise for Programming (Coding) [Stacks] Download and unpack (unzip) the file Stacks.rar....
Topics Arrays Accessing Arrays Description Write a C++ program that will display a number of statistics...
Topics Arrays Accessing Arrays Description Write a C++ program that will display a number of statistics relating to data supplied by the user. The program will ask the user to enter the number of items making up the data. It will then ask the user to enter data items one by one. It will store the data items in a double array. Then it will perform a number of statistical operations on the data. Finally, it will display a report...
Please answer the following Case analysis questions 1-How is New Balance performing compared to its primary...
Please answer the following Case analysis questions 1-How is New Balance performing compared to its primary rivals? How will the acquisition of Reebok by Adidas impact the structure of the athletic shoe industry? Is this likely to be favorable or unfavorable for New Balance? 2- What issues does New Balance management need to address? 3-What recommendations would you make to New Balance Management? What does New Balance need to do to continue to be successful? Should management continue to invest...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT