Time complexity of this function?

algo(n)
   for i in 0 to n {
      for 0 to 8^i {
      }
   }
   for i to 8^d {
   }

Any kind of analysis or information about the time complexity of this algorithm will be usefull. Worst case, best case, lower/upper bounds, theta/omega/big-o, recurrence relation....etc.

---

Your algorithm runs in exponential time ( T ∈ Θ(c^n) , c>1 ). You can analyse the number of iterations of the inner for loop ( ... for 0 to 8^i ) using Sigma notation:

Since your algorithm is in Θ(8^n) , it is also in O(8^n) (upper asymptotic bound) and Ω(8^n) (lower asymptotic bound).

---

The above analysis is performed under the assumption that the d in the final for loop analysis is less or equal to n , in which case the nested two for loop prior to it will dominate (and hence we needn't analyze the last non-dominant for loop explicitly).

---

algo(n) is basically made of two parts:

   for i in 0 to n
      for 0 to 8^i

and

   for i to 8^d

Let's start with the first. Assuming each iteration of the inner loop takes constant time, it's complexity is C*8^i . Now, if we sum it across possible values of i we get:

8^0 + 8^1 + 8^2 + .... + 8^n-1

This is sum of geometric series with a=1, r=8 , and its sum is:

1 * (1-8 ^(n-1)) / (1-8) = 1 * (-1/7 + 8^(n-1)/7) 

For n->infinity , this can be approximated as 8^(n-1)/7 , and we can conclude the complexity is Θ(8^(n-1)/7) = Θ(8^n)

As for the 2nd part, it is pretty straight forward and is 8^d.

This gives total complexity of T(n) is in Θ(8^d + 8^n)

链接地址: http://www.djcxy.com/p/40178.html

上一篇: 大哦和欧米茄符号之间的区别究竟是什么？

下一篇: 这个功能的时间复杂度？