*1) find the second biggest number in a given array of size n. you have to use n+logn number of searches or less
By this you want to have a complexity less than or equal to n + log n rite?
Consider an array { 17 , 4, 3, 18 , 9 , 15, 6 }
max1 & max2 are index in array.
Iteration 1:->i=1 ( as neither arr[max1] < arr[i] nor arr[max2] < arr[i] )
so no change
max1 i
17 4 3 18 9 15 6
max2
Iteration 2:->i=2 ** ( as neither arr[max1] < arr[i] nor arr[max2] <
arr[i] ) so no change
**max1 i
17 4 3 18 9 15 6
max2
**
**Iteration 3:->i=3 ** ( as arr[max1] < arr[i] change max2 to max1 )
* * i
17 4 3 18 9 15 6
max2 **max1
**Iteration 4:->i=4 ** (**as neither arr[max1] < arr[i] nor arr[max2] <
arr[i] ) so no change)
* * i
17 4 3 18 9 15 6
max2 **max1
**Iteration 5:->i=5 ** (**as neither arr[max1] < arr[i] nor arr[max2] <
arr[i] ) so no change)
* * i
17 4 3 18 9 15 6
max2 **max1
**Iteration 6:->i=6 ** (**as neither arr[max1] < arr[i] nor arr[max2] <
arr[i] ) so no change)
* * i
17 4 3 18 9 15 6
max2 **max1
**Second biggest number is arr[max2]
Complexity is O(n)*
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
secondbiggestnumber.cpp
Description: Binary data
