CODEWITHSUNDEEP
c#algorithm
Programm-ist
Programm-ist

Reputation: 109

the Time complexity of an algorithm

I am learning algorithms at the moment and wrote this below code, which finds if a peak exists in a one dimensional array. my question is how do I know its time complexity of its best case or average case?

The worst case time complexity (if the element of the array are sorted) is O(n), but if the array is not sorted and it has 10 elements the code runs 5 loops to get the result, which is half of the array size, so can anyone tell me how to write this in algorithmic notation.

 int[] arr = { 1,5,2,7,8,9,4,6,7};
 int peak;

 int count = 0;
 for (int i = 1; i < arr.Length - 1; i++)
 {
            peak = -1;
            if (arr[i - 1] <= arr[i] && arr[i] >= arr[i + 1])
            {
                peak = arr[i];
                i++;
            }
            else if (arr[i - 1] >= arr[i] && i - 1 == 0)
            {
                peak = arr[i - 1];
            }
            else if (arr[i + 1] >= arr[i] && i + 1 == arr.Length - 1)
            {
                peak = arr[i + 1];
            }

            if (peak != -1)
                listBox1.Items.Add(peak.ToString());

            count++;
}

listBox1.Items.Add(count.ToString());

Upvotes: 1

Views: 319

Answers (1)

Dylan Lawrence
Dylan Lawrence

Reputation: 1533

You would still write it as O(n) because Big-O is worst case (which here is linear time.) In this case n is of course the array length. Theoretically nothing inside your loop exceeds O(1) (I'm going to ignore the list append and call it constant.)

After noticing your comments about n/2 iterations. n/2 is the same as saying (1/2)n or O((1/2)n) this is equivalent to O(n) because we ignore all coefficients when doing bounding with Big-O.

Upvotes: 3

Related Questions