I think it actually depends upon the f(counter) function. what if f(0) is the terminating condition and takes constant time but if f(1) is called then it will take ø(m).
1.) Consider an Array A[5] = { 1,1,1,1,1 }
at index 0 : A[0] =1,then counter is incremented , counter = 1.
at index 1 : A[1] =1, then again counter is incremented, counter = 2.
..similarly counter = 5 at the end. Total Time complexity = constant for every element in this array, if there are N elements in the array and all are 1 then Time Complexity for such case - O(N).
2. )Consider an Array A[5] = { 0,0,0,0,0 } ( You might think this is the worst case but its not )
at index 0 : A[0] =0 ,then else part f(0) is called which takes constant time. because counter is already 0 intially and f(0) is the terminating condition as assumed above.
at index 1 : A[1] =0, then again else part f(0) is called which again takes constant time.
... and this continues till the end. Total time complexity = constant for every element in this array, if there are N elements in the array and all are 0 then Time complexity for such case - O(N).
3.) Consider an Array A[5] = {1,1,0,0,0}
at index 0: A[0] = 1, counter =1 takes constant time 'c'
at index 1: A[1] = 1, counter =2 takes constant time 'c'
at index 2: A[2] = 0, f(2) is called which takes ø(m) time. and then counter is set to 0 and takes ø(m) time
at index 3: A[3] = 0, f(0) is called which takes constant time 'c'
at index 4: A[4] = 0, f(0) is called which again takes constant time 'c'
Total Time complexity = c + c + ø(m) + c + c = 4c + ø(m) . In case there are N elements where first few elements are 1's followed by continuous 0's. then for elements from starting upto all 1's in the array takes constant time and then for first 0 it takes ø(m) time and for the remaining 0's it takes constant time. Total time Complexity = c + c + c--- + c ( all 1's) + ø(m) ( first 0 encountered) + c + c + --- +c ( remaining 0's) = (N-1)*c + ø(m) = which will be O(N) + ø(m) = Max ( O(N) +O(m) )
4.) Consider an Array A[5] = { 1,0,1,0,1 }
at index 0: A[0] = 1, counter =1 takes constant time 'c'
at index 1: A[1] = 0, f(1) is called which takes ø(m) time. and then counter is set to 0.
at index 2: A[2] = 1, counter = 1 takes constant time 'c'
at index 3: A[3] = 0, f(1) is called which takes ø(m) time. and then counter is set to 0.
at index 4: A[4] = 1, counter =1 takes constant time 'c'
Total time complexity = c + ø(m) + c + ø(m) + c = 3c + 2 * ø(m) = Ceil(5/2) * c + Floor(5/2) * ø(m)
If there are N elements and the array consists of Alternate 1's and 0's then almost half of the elements will takes constant time and other half will call f(1) which takes ø(m). Total = (N/2)*c + (N/2) * ø(m) = O(N*m).
Hope it helps :)
please correct me if wrong :)