I have a sorted array of length `n`

and I am using linear search to compare my value to every element in the array, then i perform a linear search on the array of size `n/2`

and then on a size of `n/4`

, `n/8`

etc until i do a linear search on an array of length 1. In this case n is a power of 2, what are the number of comparisons performed?

Not sure exactly if this response is correct but I thought that the number of comparisons would be

T(2

^{n}) = (n/2) +(n/4) + ... + 1.

My reasoning for this was because you have to go through every element and then you just keep adding it, but I am still not sure. If someone could walk me through this I would appreciate it

The recurrence you have set up in your question is a bit off, since if n is the length of your input, then you wouldn't denote the length of the input by 2^{n}. Instead, you'd write it as n = 2^{k} for some choice of k. Once you have this, then you can do the math like this:

- The size of half the array is 2
^{k}/ 2 = 2^{k-1} - The size of one quarter of the array is 2
^{k}/ 4 = 2^{k-2} - ...

If you sum up all of these values, you get the following:

2

^{k}+ 2^{k-1}+ 2^{k-2}+ ... + 2 + 1 = 2^{k+1}- 1

You can prove this in several ways: you can use induction, or use the formula for the sum of a geometric series, etc. This arises frequently in computer science, so it's worth committing to memory.

This means that if n = 2^{k}, your algorithm runs in time

2

^{k+1}- 1 = 2(2^{k}) - 1 = 2n - 1

So the runtime is 2n - 1, which is Θ(n).

Hope this helps!

Similar Questions

How to find the median of M sorted arrays of integers? Where the size of each array is bounded by N. Assume that each array contains sorted integer elements. There are two variation of this question.

I have a large sequence of random integers sorted from the lowest to the highest. The numbers start from 1 bit and end near 45 bits. In the beginning of the list I have numbers very closer to each oth

This question was asked to me in one of my job interviews - M is a 2d n-by-n matrix in which every row and every column is sorted, and all the matrix elements are different. I need an O(n) algorithm

Let's say I have an Array ary = [0.0, 1.0, 5.0, 1.0, -2.0, 3.5], and I want as output another array of the same size containing ary's indices in sorted-by-value-order. In other words, the output shoul

I have an array whose keys are in the format [A1] -> [A20], [B1] -> [B20], etc, and I'm trying to sort that array using first ksort() (to get the letters in the correct order) and then uksort().

Possible Duplicate: The intersection of two sorted arrays we have two sorted arrays A and B, besides compare one with all the elements in other array, how to design a best algorithm to find the arra

I know that the definition of suffix array itself is that its a sorted array of all the suffixes of a string. But I am trying to understand whats the significance of this sorting operation here? Suppo

Which sort algorithm works best on mostly sorted data?

I'm developing aprogram, for which I need an array generation algorithm, however, even though the code should work, all the entries are exactly the same, as can be seen by the System.out.println(); ne

Hi I have an array of distances a= np.array([20.5 ,5.3 ,60.7 ,3.0 ], 'double') and I need the indices of the sorted array (for example [3, 1, 0, 2], for a.sort()). There is a function in numpy to do t

There seems to be a problem in add method of the class I have written.. I want to make a SortedList using an array, but I can't figure out what the problem is. This is my code: public class SortedList

Internet seems to be full of similar (solved) questions. But non of these realy fit. I have an Array of Strings and want to count the occurancies of any single String. I have already sorted it. (Its a

I'm coming over to Xcode from visual studio and am having some trouble inspecting or examining variables at my breakpoints. Often times I'll try to examine an object by mouse-over and and expand out i

Is there any way to maintain a sorted array of objects? For example, if I have an object with properties ID, Date, Name and a collection of these objects: $col = array(); public function addNewObject(

I have to develop an algorithm that will be able to sort a n-element list, where the first (n- root(n)) elements are sorted. Yes, this is a homework question. After some research on the internet and

Considering there is an array returned from a function which is of very large size. What will be the fastest approach to test this ? A simplest approach will be: /// <summary> /// Determines i

In this post Why is processing a sorted array faster than random array, it says that branch predicton is the reason of the performance boost in sorted arrays. But I just tried the example using Python

Can anybody optimize following statement in Scala: // maybe large val someArray = Array(9, 1, 6, 2, 1, 9, 4, 5, 1, 6, 5, 0, 6) // output a sorted list which contains unique element from the array with

In R, given an numeric array, how to produce another array which contains sorted index order into the original array? To clarify my question, consider an example: For an original array: [33 11 55 22 4

I am not able to get a proper sorted output in case of a bubble sort algorithm when implemented in the Windows Store App (Javascript) . Below is the source code for Javascript :- function BubbleSort()

I found this question on an online forum: Really interested on how it can be solved: Given an array A of positive integers. Convert it to a sorted array with minimum cost. The only valid operation are

I need to do the following: Given an std::vector of int I need to replace each int by the index that it would be in if the vector were sorted. I will try to explain it better with an example. Input: {

What is the fastest and most efficient way to do this: word = dinosaur newWord = word[0] + ''.join(sorted(word[1:])) output: dainorsu Thoughts: Would something as converting the word to an array

I got this problem from an interview with Microsoft. Given an array of random integers, write an algorithm in C that removes duplicated numbers and return the unique numbers in the original array. E

I need to transform an array to html table sorted by time, add rank and calculate time loss for the first place. Array example:` var array = [ [McNulty Oscar, USA, 108:45.1], [Johansson Anton,

I am developing a Catalyst app which uses Template::Toolkit as template engine. One page needs a list of equal input elements. They can be taken from an array but I need both sort order and a descript

Let w be an array of length n. Write a divide and conquer algorithm in java to determine the number of times 3 consecutive identical caracters appear. Below is the algorithm I've written. The answer s

I have created a Balanced BST from a sorted array, my question is how to test it. Simply testing that if a tree is balanced or not will not help, as even a binary tree (note - mentioned Binary tree, n

Let me start by saying this a homework question that I am having trouble with. I have sorted an array and what I need to do is use another array to remove duplicates by iterating over the first and co

In Programming Pearls (second edition) Column 5, problem 5 the question is about implementing binary search on an unsorted array. How can you add partial checking to the function at significantly les

There is a sorted array which is of very large size. In it every element is repeated more than once except one element. How can I find the unrepeated element in O(log n) time complextiy.

I have voiceResults in an array to search for a contact: Ben McDonald Ben MacDonald Ken McDonald Ken MacDonald I have established the potentialMatches (example) in another array: Ben McDonald Benjami

How can I check if TArray is already sorted? I am using the default TArray.Sort to sort my array.

I apologize if this has been asked here - I've hunted around here and in the Tentative NumPy Tutorial for an answer. I have 2 numpy arrays. The first array is similar to: 1 0 0 0 0 2 0 0 0 0 3 0 0 0 0

I already read this post but the answer didn't satisfied me Check if Array is sorted in Log(N). Imagine I have a serious big array over 1,000,000 double numbers (positive and/or negative) and I want

I've seen it mentioned on the Internet. What is a 'circularly sorted array'?

Does an algorithm exist that finds the maximum of an unsorted array in O(log n) time?

Here is a piece of C++ code that seems very peculiar. For some strange reason, sorting the data miraculously makes the code almost six times faster: #include <algorithm> #include <ctime> #

Interesting algorithm I would like to get the communities opinion on. I am looking to loop through a Sorted ArrayList<String> for the boolean result if a String exists in the array that begins w

Given an unsorted array A = a_1 ... a_n And a set of sorted Arrays B_i = b_i_1 ... b_i_n # for i from 1 to $large_number I would like to find the maximums from the (not yet calculated) sum arrays C_

I wanted to ask if there is an algorithm that can find, in an array of length n, if there is an array element with a certain frequency percentage (10%, 20% etc...) in linear time. Selection sort is O(

I wonder if there is a formal name for this algorithm and what is an elegant way to solve this: the problem is -- given an array, say, [3, 6, 2], print out all the numbers starting with 000, 100, 200,

Possible Duplicates: Merging two sorted lists Algorithm for N-way merge Given k sorted arrays each of length n, construct a single merged and sorted array.focus on running time and space complexity.

For exmple, i have undefined number of a pairs(key, value). And I want to build sorted list during iterate trough this pairs(it is long operation). I think to use a BinaryTree as a sorted structure an

I am trying to sort an array which has properties like it increases upto some extent then it starts decreasing, then increases and then decreases and so on. Is there any algorithm which can sort this

Can somebody PLEASE answer my specific question, I cannot use material not covered in class yet and must do it this way. I'm trying to iterate over a sorted array and if the previous number == the cu

I have a multidimensional array of dates, strictly an ArrayList<ArrayList<Date>>. I need to generate a new single-dimensional ArrayList<Date> made up of the items in all the arrays o

I'm a beginnner. This might sound stupid, as its a simple algorithm.The below program compiles successfully but when I run it does not prints the sorted array.The code works fine till the sort algorit

I keep getting a null pointer exception. However, the reason eludes me. Can someone help? EDIT: I am using an Integer[][] array to represent null values as infinity symbols as floyd's algorithm is r

I want to implement an algorithm that inserts sorted arrays into binary search trees but I don't want ending up with a tree that only grows to one side. Do you have any ideas? Thanks.