CODEWITHSUNDEEP
algorithmfor-loopindexingtimetime-complexity
GccGUY
GccGUY

Reputation: 369

What is following time complexity?

If a for loop is defined as for (int i = 2; i < n; i = i*i + i) What the "i*2+i" represents for time complexity. What is time complexity in big-O notation? How could I solve big-O notation for this increasing index? Ex: i = 2 , 6 , 42 , 1086 , .... (general formula "i*2+i")

Upvotes: 0

Views: 134

Answers (1)

user1196549
user1196549

Reputation:

As i has a concrete type (int), it is bounded and the complexity is perforce O(1).

In addition, the function is so fast growing that the capacity of an int is exceeded as of the sixth term.

If one considers that the given code is pseudocode and that the ints are unbounded, then one may use

i[k]² <= i[k+1] = i[k]² + i[k] <= a i[k]²

where a is a constant to be determined.

Then taking the base-2 logarithm

2 lg i[k] <= lg(i[k+1]) <= 2 lg(i[k]) + lg(a)

and by induction

2^m lg(i[k]) <= lg(i[k+m]) <= 2^m lg(i[k]) + (2^m - 1) lg(a) <= 2^m lg(a.i[k])

Taking the logarithm again,

m + lg(lg(i[k])) <= lg(lg(i[k+m])) <= m + lg(lg(a.i[k]))

also written

lg(lg(i[k+m])) - lg(lg(a.i[k])) <= m <= lg(lg(i[k+m])) - lg(lg(i[k]))

As m represents the number of iterations following the k first, for n = i[k + m] we have

lg(lg(n)) - lg(lg(a.i[k])) <= m <= lg(lg(n)) - lg(lg(i[k]))

In particular, with k=0, we can take a = 3/2 and

lg(lg(n)) - lg(lg(3)) <= m <= lg(lg(n)) - lg(lg(2))

This proves m = Θ(lg(lg(n)).

Upvotes: 3

Related Questions