0

I face a question: T(N) = T(sqrt(N)) + 5.

I am wondering can I solve it in this way?

T(N) = O(sqrt(N)) + O(5)

Since O(5) = O(1) is a constant, we can ignore it.

So the big O notation of T(N) is O(N^(1/2)).

Or can I just say its notation is O(N) as there is no big difference between O(N) and O(sqrt(N)).

Thank you!

Gareth Lam
  • 145
  • 1
  • 4
  • 13
  • Shrinking by a square root is a hallmark of [O(log log n)](https://stackoverflow.com/questions/16472012/what-would-cause-an-algorithm-to-have-olog-log-n-complexity) complexity. – templatetypedef Oct 01 '17 at 17:25

2 Answers2

3

(For neatness, let's replace the 5 with a constant c)

Substituting this function into itself multiple times, we can spot a pattern emerging:

enter image description here

When do we stop iterating? When the stopping condition is met. Take this to be n = 2 (not 1 as is usually the case, since the argument is asymptotic to n = 1):

enter image description here

So the final cost of this function is:

enter image description here

Note that the constant c (= 5) does not matter in terms of asymptotic complexity. (And also that the result is not simply log n but log log n)

EDIT: if you were to choose a different stopping condition n = a, a > 1, then the above step would become:

enter image description here

Which only differs by a constant from the original result.

meowgoesthedog
  • 14,670
  • 4
  • 27
  • 40
  • I would like to know how to choose the value of n for the stopping condition? Is it ok to take n = 3/4/5? It seems that the result is the same(also loglogn). – Gareth Lam Oct 02 '17 at 03:37
  • Yes, choosing a different stopping condition would result in a different *base* for the **inner** logarithm (outer logarithm is still base 2) - this corresponds to a multiplicative factor inside the outer logarithm, and thus an additive constant outside, which can be ignored. – meowgoesthedog Oct 02 '17 at 09:05
2

Edit: I made a mistake in the original answer, assuming that n is a power of 2 and reducing the recurrence to 1, 2, 4, ... n, which is wrong. I apologize for the misleading. Here is the updated answer.

From,

T(n) = T(sqrt(n)) + 5,

we can also write it as:

T(n) = T(n^(1/2)) + 5,

then by recurrence:

T(n^(1/2)) = T(n^(1/4)) + 5,

T(n^(1/4)) = T(n^(1/8)) + 5,

...

T(n^(2^-m)) = T(n^(2^-(m+1)) + 5,

this doesn't show a constant where we can stop. Therefore we need to substitute n.

Try:

n = 2^(2^m),

where we have

m = log log n

starting from m = 0, which is n = 2,

then we have:

T(n) = T(2) + 5 + 5 + ... + 5,

how many 5s are there? We count like this:

2^(2^0), 2^(2^1), 2^(2^2), ... 2^(2^m)

So there are m 5s, where m = log log n. So

T(n) = T(2) + 5 log log n,

which is,

T(n) = O(log log n).

Community
  • 1
  • 1
pjpj
  • 441
  • 1
  • 4
  • 20
  • I am confused with a point. How to get T(2) = T(1) +5? Since T(1) = T(1) +5 and T(2) = T(2^(1/2)) +5, it seems that T(2) isnt equal to T(1) +5. – Gareth Lam Oct 01 '17 at 15:38
  • @GarethLam Yeah... you are right. Technically speaking it is not that clear. But here you can just ignore that... no one will ask you what T(1) and T(2) are (here T(1) doesn't even exist strictly...). Point is, we can just treat T(1), T(2) or whatever T(c), where c is a constant, as a constant, which in asymptotic terms, is O(1). Remember in Big O notation, we don't calculate accurate values like solving equations, instead, for example, we use `log n` instead of `log_2^n` or `log_10^n`. It's the *order* that matters. – pjpj Oct 01 '17 at 15:51
  • Alright，i think this part is ok for me. But how about the counting part. Why use logn instead of n? – Gareth Lam Oct 01 '17 at 16:17
  • 1
    This analysis is incorrect. The recurrence should solve to Theta(log log n). – templatetypedef Oct 01 '17 at 17:24
  • @GarethLam Sorry for the mistake. See my updated answer. – pjpj Oct 02 '17 at 05:17