The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+4 votes

Simple linear search to find max min algo

maxmin(a,n,max,min) { max=min=a[1]; for i=2 to n do { if a[i]>max then max:=a[i]; else if a[i]<min then min:=a[i]; } }

1.Average case complexity of the above algo given that the first if conditions fails for n/2 elements

2.Average case complexity of the above algo if the first condition fails 1/2 times

plz xplain

+4 votes

Best answer

Complexity of the algorithm is O(n) and is irrespective of the success of if case as both if as well as else are O(1) operations.

If you say exactly, the complexity in terms of comparisons will be

1. $n-n/2-1$ (number of elements for which first if succeeds) $+ 2 \times (n/2) $ (number of elements for which first if fails)

$= 3n/2 -1$

2. $ (n-1)/2 + 2\times (n-1)/2$

$=3(n-1)/2$

If you say exactly, the complexity in terms of comparisons will be

1. $n-n/2-1$ (number of elements for which first if succeeds) $+ 2 \times (n/2) $ (number of elements for which first if fails)

$= 3n/2 -1$

2. $ (n-1)/2 + 2\times (n-1)/2$

$=3(n-1)/2$

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.9k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 949
- Others 1.3k
- Admissions 409
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,781 questions

41,758 answers

118,936 comments

41,400 users