CODEWITHSUNDEEP
algorithm
user3287154
user3287154

Reputation: 69

What is worst case running time for the given algorithm

I have been asked this question in my academic paper. please let me know the answer? 

 arrayFind(x, A)
    i =0 ;
    while( i < n ) {
       if(x==A[i])
           return i;
       else 
           i = i+1; 
   }
 return –1;

Suppose we have an algorithm, find2D( ), to find an element x in a two dimensional n x n array A. The algorithm find2D( ) iterates over the rows of A and calls the algorithm arrayFind() on each one until x is found or it has searched all rows of A.

What is the worst case running time of this algorithm

a. If the elements in each row are sorted?
b. If the elements in each row are not sorted ?

Upvotes: 2

Views: 352

Answers (1)

markusthoemmes
markusthoemmes

Reputation: 3120

With the information given, sorting/not sorting has no effect to the worst case scenario. In both cases the worst case would be, that the latest element in the latest row is the one to find. In that case the runtime will be O(n^2), where n has the meaning you pointed out with n x n. It's n x n because you have to iterate over n rows and then make n comparisons in each row.

If you would use a Binary Search, the sorted example would have a worst case runtime of O(n log n) and the worst case would be, that the searched element is in the middle of the last row.

Upvotes: 5

Related Questions