CODEWITHSUNDEEP
algorithmtime-complexity
Edward
Edward

Reputation: 1

Time complexity of this algorithm? How to analysis？

Time complexity of this algorithm? How to analysis？

int fun(int n)
{
          int i = 0, j = 0, m = 0;
          for (i = n; i > 0; i /= 2)
          {
                   for (j = 0; j < i; j++)
                   {
                             m += 1;
                   }
          }
          return m;
}

Upvotes: 0

Views: 28

Answers (1)

Luka
Luka

Reputation: 156

Your running time is Sum_i (n/2^{i}), for i in {0 to log(n)}. n is the leading term, thus O(n). The sum will not exceed 2n.

Upvotes: 1

Related Questions