Question

Time Complexity: Build a table in Excel and record the time complexity taken by linear and binary search to look for an element with the following array sizes: 10, 50, 100, 200, 500, 700, 1000. Compare the performance of both algorithms highlighting the time complexity for both algorithms when run on small input size and when run on large input size.

To accomplish this, load a list with the file data and then create a program that selects at random X amount of elements from the original list (where X is a value that the user selects) and place them in an array, then select at random an element in the original list to search in the sampled array using both algorithms. Measure the time it takes for both algorithms on an array of a given input size.

Answer 1

1) Below code is written in python3 and use online compiler to run it

" https://www.onlinegdb.com/online_python_compiler"

It randomly creates array of sizes [10, 50, 100, 200, 500, 700, 1000] sorts them then randomnly chooses an integer from each array and then time complexity is calculated for both Linear search and Binary search. They are then stored in a csv file for excel called table. Thus now we can compare the time complexity for both algorithms when run on small input size and when run on large input size.

import numpy as np
import time
import random
import csv

def LinearSearch(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
  
def BinarySearch(arr, l, r, x):
   while l <= r:
       mid = int(l + (r - l)/2);
       if (arr[mid] == x):
           return mid
       elif arr[mid] < x:
           l = mid + 1
       else:
           r = mid - 1
   return -1

ls_size = [10, 50, 100, 200, 500, 700, 1000]

time_linear_search = []
time_binary_search = []

for i in range(len(ls_size)):
gen_rand_arr = np.random.randint(1,10000,ls_size[i])
gen_rand_arr.sort()
  
x = random.choice(gen_rand_arr)

start_time = time.time()
result = LinearSearch(gen_rand_arr,x)
end_time = time.time()
time_linear_search.append(end_time- start_time)

start_time = time.time()
result = BinarySearch(gen_rand_arr, 0, len(gen_rand_arr)-1, x)
end_time = time.time()
time_binary_search.append(end_time- start_time)

print(time_linear_search,time_binary_search)

with open('table.csv', 'w') as f:
writer = csv.writer(f)
writer.writerows(zip(time_linear_search, time_binary_search))

2) load a list with the file data and then create a program that selects at random X amount of elements from the original list (where X is a value that the user selects) and place them in an array, then select at random an element in the original list to search in the sampled array using both algorithms. Measure the time it takes for both algorithms on an array of a given input size.

As there is no file here random data is generated with 10000 elements. Then user can enter the value of X (size of array). Here the below program selects X elements from above generated array then a random number is generated to search by both methods and outputs time complexity of the same.

import numpy as np
import time
import random
import csv

def LinearSearch(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
  
def BinarySearch(arr, l, r, x):
   while l <= r:
       mid = int(l + (r - l)/2);
       if (arr[mid] == x):
           return mid
       elif arr[mid] < x:
           l = mid + 1
       else:
           r = mid - 1
   return -1

gen_rand_arr = np.random.randint(1,10000,10000)
# gen_rand_arr
print(type(gen_rand_arr))
X = input("Enter value of X (size of array) less than 10000 : ")
array_search = gen_rand_arr[:int(X)]
x = random.choice(gen_rand_arr)

start_time = time.time()
result = LinearSearch(array_search,x)
end_time = time.time()
time_linear_search = end_time- start_time

start_time = time.time()
result = BinarySearch(array_search, 0, len(array_search)-1, x)
end_time = time.time()
time_binary_search = (end_time- start_time)

print("Time complexity for linear search and binary search are : ",time_linear_search,time_binary_search)