Question

The maximum number of searches required by the binary search algorithm to search an ordered list of n items, where n is a power of 2, what is the time complexity?

Answer #1

Let us consider n=1000..

and in worst case scenario we are searching for the element
stored in the o^{th} index then it will search for 10 times
to reach it.

As 1000/2=500.

500/2=250.

250/2=125.

125/2=62.

62/2=31.

31/2=15.

15/2=7.

7/2=3.

3/2=1.

1/2=0.

**There by if there are n elements exists in a sorted
array,then maximum number of comparisons may require is
log _{2}n.**

*Explanation:*

Binary Search Algorithm is known as half interval search or the logarithmic search which finds the position of the target value within a sorted array only.

It starts with the middle element of the array and if the target value matches with the middle element then it is the best case possible in O(1).

If it does not match with the current middle value then it compares with the value stored in the middle index.

If the value in the middle index is greater than the target value then the search goes to the right side of the array and if the value in the middle index is lesser than the target value then the search goes to the left side of the array.

**Algorithm**

1. Set L to 0 R to n-1

2. If L>R,then search terminates as unsuccesful.

3.Set m ( the position of the middle element) to the floor(largest prev integer) to (L+R)/2

4. If target=A_{m} ,the search is done.

5. If target>A_{m} ,set L to m+1 and go to step 2

6. If target<A_{m} set L to m-1 and go to step 2

**Time
Complexity**

**T(n)=T(n/2)+1 if n>1**

**T(n)=1 if n=1**

**There by T(n)=O(log _{2}n)**

what is the largest number of entries that are interrogated if the
binary search algorithm is applied to a list of 4000 names? how
does this compare to the sequencial search?

Explain Binary Search Algorithm to search for V
= 75, using the data given below
5, 10, 25, 35, 45, 50, 60, 70, 75, 80, 85
How many searches will be needed?

Complete the following table by specifying algorithm efficiency
for : Selection sort, Insertion sort, Binary search, and Linear
search. (Efficiency can be one of : log n, n, n2). List
algorithms from the most efficient (fastest) to the least efficient
(slowest).
ALGORITHM
EFFICENCY
1 most efficient (fastest)
2
3
4 least efficient (slowest)

a) Design a recursive linear-time algorithm that tests whether a
binary tree is a binary search tree. Describe your algorithm in
English or with a simple pseudocode program. b) (3 bonus pts.)
Extend the algorithm in a) to test whether a binary tree is an AVL
tree.

Select All true answers about linear and binary search
1. The advantage of linear search is that it runs in O(1) space
complexity and binary search can only run in O(logn) space
complexity
2. The disadvantage of binary search is that it requires the
container to be sorted which linear search does not.
3. The advantage of binary search over linear search is that is
more efficient O(logn)versus O(n) average/worst case).
4. The advantage of linear search is that it...

State True or False. i) Binary search is used for searching in a
sorted array. AND ii) The time complexity of binary search is O(log
n). A) True, False B) False, True C) False, False D) True, True
Explain

Python: Write a program that performs a logarithmic search on an
ordered list of 1000 elements. The search on the list should be on
a randomly generated number between 1-1000.

Python: Write a program that performs a sequential search on an
ordered list of 1000 elements. The search on the list should be on
a randomly generated number between 1-1000.

How to measure the time complexity of an
algorithm?
Identify an important operation in the algorithm that is
executed most frequently.
Express the number of times it is executed as a function of
N.
Convert this expression into the Big-O notation.
A. For each of the three fragments of code, what is its
worst-case time complexity, in the form "O(…)". (Use the
given solution to the first problem as a
model)
//----------------- This is a sample problem – solved
------...

Given the list of values below, create a Binary Search Tree for
the list, Use the first value in the list as the root of the tree,
add the nodes to BST in the order they appear in the list.[50, 44,
82, 39, 35, 98, 87, 100, 74, 23, 34, 14, 94]
What is the minimum height of a Binary Tree that contains
24nodes?
What is the minimum height of a Binary Tree that contains
64nodes?
What is the minimum...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 35 minutes ago

asked 38 minutes ago

asked 56 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago