I'm trying to find time complexity $T(n)$ of the algorithm by a given pseudocode:
1: for i:=1 to N do 2: begin 3: len := 1 4: while i - len >= 1 and i + len <= N do 5: begin 6: if a[i] > a[i - len] and a[i] > a[i + len] then 7: len := len + 1 8: else 9: break 10: end 11: print(i, len) 12: end
I know that the answer is $T(n) = O(n\log n)$ but I struggle to prove that.
From the pseudocode its clear that this algorithm is designed to find the longest subarray with each element smaller then the middle one. (actually this algorithm prints the length of such array for each array element)
I can't prove it formally because I struggle with the content-dependent loop at 5-10, but informally I went like this: Lets construct the array which will be the worst case for this algorithm.
For the sake of simplicity lets use array with 15 elements and start with array filled with zeros: $$0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0$$ external loop will execute 15 times and each time the loop 5-10 will perform a single comparison Now we will do the following: we divide array in two and put maximum value in the middle. Then for each half we will do the same, except the value will be decresed by 1.
We will get the following array: $$0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0$$
Now, intuitively I can see why this is the worst case for the algorithm and where $logn$ comes from, but I can't prove it properly.
As a side note I would appreciate any pointers toward where one can practice these kind of problems (concrete algorithms time complexity analysis, preferably with answers/explanations)