Java Programming+Report

Introduction

Description of Algorithms

When we analyze this algorithm we see that there is a double sum that occurs,

n-2 n-1

∑ ∑

outer_index = 0 inner_index = outer_index + 1

Computing the sums we find that the selection sort is of Θ(n2) for efficiency.

Lastly,

Setting up a recurrence relation of floor(n/2) + 1 for n > 1 and n = 1 resulting in 1, we can find that the efficiency of the binary search is Θ(log n).

General Process

The main, sort, and search algorithms general process flow is illustrated in the following flowcharts respectively.

Main Algorithm Flow

sortArray() Flow

binSearch() Flow

Results

The run was obtained from an Apple iMac running OS X Version 10.5.6, with a 2.8 GHz Intel Core 2 Duo, and 2GB 800MHz DDR2 SDRAM.

Algorithm	Order of Growth	Time(ms)
Generation of Random Numbers	Θ(n)	2.066
Sorting of Array	Θ(n2)	112.472
Search for Number 100	Θ(log n)	0.059

Conclusion