Purchase Solution

Proving O(log n) comparisons in key compaisons binary search

Not what you're looking for?

Ask Custom Question

Prove that any binary search algorithm on a sorted array of size n that uses only key comparisons must require at least omega (log n) comparisons in the worst case.

Purchase this Solution
Solution Summary

A binary search tree proof is provided. A comparison is proved for the binary searches.

Solution Preview

Proof:
Suppose the sorted array is A with size n. That is A[1], A[2], ..., A[n].
According to the binary search, in the worst case, the root A[1] ...

Purchase this Solution
Free BrainMass Quizzes
Word 2010: Table of Contents

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.

Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

C# variables and classes

This quiz contains questions about C# classes and variables.

Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.

Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

View More Free Quizzes
Related BrainMass Solutions

  • heap structure

    than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime.

  • Detailed comparision of linear and binary searches on a list

    The binary search, O(log n), would require about log2(32) searches. That is, 5 searches. The binary search is faster by a small amount. But consider a larger n. Suppose that n = 1,000,000 (one million).

  • Hashing: separate chaining method

    Below, "n" refers to number of elements in the linked list / balanced binary search tree, and "lg" refers to log-base-2. Adding a new node in linked list is constant time i.e.

  • tree structure search and update

    Then the height of the tree, h, is log(n). As a result, the search operation on this tree is O(h), that is O(log n), as we have to search at most h nodes.

  • Runtime Analysis of Search Algorithm

    A binary search would involve first sorting the array, which can be done in time O(log n), and then looking for the number 19 in the middle of the array.

  • Comparisons

    To place this new name in its place in the alphabetical list, the number of comparison is (log_2 n), which means log of n with base 2.

  • Significant Inversions Algorithm : Inversion Pairs

    Find the position of each element of S in S' using binary search.

  • C++ big O notation

    So the running time of this algorithm is said to be O(log n). In other words: **Given a sorted list of n numbers and a target number, binary search takes O(log n) steps to find the target.

  • NP - Completeness Minimization Problem

    By the binary recursive search, the optimal cost is between 1 and n^4, thus CostOfP1 will be called log(n^4) = 4logn times. Each time in CostOfP1, A(k,m) is running at most once and it takes O(nlogn) time.

View More Related Solutions