Hello ppl.
Ok have to investigate and write a report on the efficiency of the following Linear Search algorithm.
But im having problems starting off.... can anyone here help me kick start this 3 page report... would apreciate any information & help you guys here can give.

//   This program randomly generates a series of test data of 

// differing sizes 

//   (5 - 100 positive integers) reading them into array a. 

//   It then randomly generates a search key 

//   and searches the elements of the array using linear search. 

//   It returns a table giving the amount of data the test was 

//   run on and the number of comparisons made. 



#include <stdlib.h>     

// Make standard library available eg for random number 

// generation functions 

#include <stdio.h>     // Make input/output  library available 

#include <time.h> 


// define a new type called SearchResult  

//(like int is already a type) 

//There are two values (like 1, 2,3 etc are values for ints) 

// of type searchResult: FOUND and NOT_FOUND 

enum SearchResult {FOUND, NOT_FOUND}; 



// List the functions in this program 

SearchResult linearSearch 

   (int array[], int key, int sizeOfData, int *comparisons); 

void fill_array(int array[], int sizeOfData); 


const int RANGE = 200; // random data used in range 0-199 


int main() 


     const int arraySize = 100; 

     int a[arraySize]; 

     FILE *resultsFile; 

     resultsFile = fopen("lsrch.dat", "w");  

     // open the file lsrrch.dat for writing ("w") 


     if (resultsFile != NULL)      // file successfully opened 


       // seed the random number generator so it gives different 

       // random numbers each time 

       srand ( time (0) ); 



       // Table headings 

       printf ("Found\t Data Size\t Comparisons Needed\n"  ); 

                    //\t puts in a tab character, \n a new line 

       fprintf(resultsFile,"Data Size\t Comparisons Needed\n"); 


       // Generate table for data of different sizes 

       // giving number of comparisons each time 


       for (int datasize = 1; datasize <= arraySize; datasize = datasize+1) 


       int count = 0;  // number of comparisons this time 

       SearchResult result; // result of this search 

       int searchKey = rand() % RANGE; 


       fill_array(a, datasize); 


       result = linearSearch(a, searchKey, datasize, &count);  

           // Note address of count passed - so by reference 

        if (result == FOUND) 

             printf("KEY FOUND \t"); 


             printf("NOT FOUND \t"); 


       // print results in a table 

       printf("%d  \t\t\t  %d\n", datasize, count); 

       fprintf(resultsFile, "%d  \t\t\t  %d\n", datasize,count); 




     fprintf(resultsFile, "File not opened\n"); 


   fclose(resultsFile); return 0; 




// generate random data in range 0-20 and fill the 

// array with it up to the given size 


void fill_array(int array[], int sizeOfData) 



     for (int counter = 0; counter < sizeOfData; counter++) 


     array[counter] = rand () % RANGE; 





// A linear search function that returns the number of 

// comparisons 

// call by value as well as a direct indication of found or not. 


SearchResult linearSearch 

      (int array[], int key, int sizeOfData, int * comparisons) 



   *comparisons = 0;  // count comparisons made 

   //Note comparisons passed by reference so use * to refer 

   //to value at that address 


   for (int counter = 0; counter < sizeOfData; counter++) 


      *comparisons = *comparisons + 1;  

                  //about to do a comparison 


      if (array[counter] == key) 

         return FOUND;     // Key found! 



   return NOT_FOUND;           // Key not found 


Again i would apreciate all help.

11 Years
Discussion Span
Last Post by Rashakil Fol

>can anyone here help me kick start this 3 page report
You have to write a 3 page report about how linear search has linear time? :?: I can summarize in two sentences. Linear search performs O(N) comparions in the worst case, and O(N/2) comparisons in the average case. The worst case is an unsuccessful search that goes through all items and the average case takes advantage of an assumed random distribution where a match will be made, on average, half way through the list.

Good luck adding the filler to that. ;)


Linear search performs O(N) comparions in the worst case, and O(N/2) comparisons in the average case.

In a related note, linear search also performs O(N/10000) comparisons in the average case!

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.