time-complexity

When can an algorithm have square root(n) time complexity?


Can someone give me example of an algorithm that has square root(n) time complexity. What does square root time complexity even mean?


Solution


  •  query(2, 14) = A[2] + A[3]+ (A[4] + A[5] + A[6] + A[7]) + (A[8] + A[9] + A[10] + A[11]) + A[12] + A[13] + A[14] ; 
     query(2, 14) = A[2] + A[3] + S[1] + S[2] + A[12] + A[13] + A[14] ;
     query(2, 14) = 0 + 7 + 11 + 9 + 5 + 2 + 0;
     query(2, 14) = 34;
    

      def update(S, A, i, k, x):
          S[i/k] = S[i/k] - A[i] + x
          A[i] = x
    

      def query(S, A, lo, hi, k):
          s = 0
          i = lo
          //Section 1 (Getting sum from Array A itself, starting part)
          while (i + 1) % k != 0 and i <= hi:
              s += A[i]
              i += 1
          //Section 2 (Getting sum from Slices directly, intermediary part)
          while i + k <= hi:
              s += S[i/k]
              i += k
          //Section 3 (Getting sum from Array A itself, ending part)
          while i <= hi:
              s += A[i]
              i += 1
      return s