Time complexity of this function?

Question

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.

Answer 1

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).