0

I am in a Data Structures and Algorithms class. I am trying to indicate if f(n) is Big Theta of g(n). I will also have to indicate Big O, small o, etc... but I am lost about the way to approach this particular pair.

f(n) = log* (log n)
g(n) = log( log* n )

From what I have currently learned, if this pair completes this statement

Θ(g(n))={f(n):there exists c_1, c_2 > 0 and n_0 <br>
 such that 0 ≤ c_1 g(n) ≤ f(n) ≤ c_2 g(n) for all n ≥ n_0}.

My problem is that I have no idea what log * is and how to use it.

tshepang
  • 12,111
  • 21
  • 91
  • 136
user3339453
  • 57
  • 1
  • 7

1 Answers1

0

I have no idea what log * is

Well, look it up. Unfortunately, Google doesn't search for symbols too well, but Googling log star turns up the iterated logarithm immediately, and SymbolHound, a search engine that doesn't ignore symbols, turns up a StackOverflow post explaining it. It's also probably in your book or course notes somewhere.

The iterated logarithm, denoted log*(n), is the number of times you need to take the logarithm of n before you get a value less than or equal to 1.

To solve the problem, consider the following. If you need to take the logarithm of n log*(n) times before you get a value <= 1, how many times do you need to take the logarithm of log(n) to do the same thing?

Community
  • 1
  • 1
user2357112
  • 260,549
  • 28
  • 431
  • 505
  • So... to indicate whether f(n) is Big Theta of g(n). Would the algebra in solving it be the same as any other log base x problem? – user3339453 Feb 22 '14 at 01:22
  • @user3339453: Not quite the same, but pretty similar. Note that `log*` isn't a logarithm, so you can't apply the usual equalities for logarithms to it. – user2357112 Feb 22 '14 at 01:23