Calculate time complexity of a pseudocode-CodePudding

I am trying to analyze the time complexity of an algorithm.

The algorithm below is meant to only check one part of the array, so no worries if it doesn't make much sense.

I am very confused about calculating the time complexity around loops, please have a look at my comments.

def search(key,arr) 
   N = arr.length                    C1
   for 0 <= i < ceiling(N/2)         C2*N C3 - ceiling can be considered a constant. 
      if(arr[i] == key):             C4*N -- Assuming this because its inside the loop?
      return 2*i                     C5*N -- N because of the loop?
   return "Not found"                C6

Does that mean we have:

T(N) = (C2 C4 C5)N (C1 C3 C6)

T(N) = C7*N (C8)

T(N) = N??

Everything inside a loop is always *N?

Thanks in advance!

CodePudding user response：

Your calculations are correct. This is an O(n) algorithm.

But you can't say that everything inside a loop is always times N. Consider the following example:

for i == N; i >= 0; i /= 2:
  ... do some constant stuff

This is obviously logarithmic in N, because we half i in each iteration.

The key is how your variable approaches the loops bound. If it increments/decrements by constant steps. Then it is linear. But if there is some other operation involved, you need to take that into account.