Question $1$: Linear search $($worst case $is(N),bestcasei{s}_{}(1)$

According to chatGPT: Searching for a key in a dataset with a billion entries is not uncommon, especially in large$-$scale

databases, distributed systems, or when dealing with big data. The efficiency of searching in such large datasets depends on the

data structure and algorithm used.

def searchlDList $($theList$,$ number$)$:

# complete your code to find the position of a key in the list

return "Not found $".k+1$

# Use the main testdriver

import time

import tumpry as np

import random

npxandomseed $(42)$

theSize $=1000000000$ # generate one billion numbers

tandomNumber Enp,random,randint $,$ size$=$theSize$)$

print$($tandonNumber$)$

print$("$ size of the list:", len$($tandomNumber$))$

print$($randomNumber$[$theSize$-1])$ # print the last int in the list

start$-$timetime$()$

answer, pos$=$search$1$DList$($randomNumber$,-5)\frac{\frac{?}{?}}{?}$ search for a non$-$ existent key $$ worst case

finish$=$timetime$()$

print $($answer$,"$ at position $",$ pos$)$

print $("$time is: $",$ str$($finish$-$start$),"$ seconds"$)$

Output:

$[121958671155131932$dots$923606556789831779]$

size of the list : $1000000000$

$831779$

Not found at position $1000000000$

time is: $154\mathrm{.}58296728134155$ seconds

Complete the following table and make your conclusion, please include the code you've used for each one along with the outputs.