Asymptotic complexity of log(n) * log(log(n))

Question

I was working through a problem last night where I had to insert into a priority queue n times. Therefore, asymptotic complexity was n log n. However n could be as large as 10^16, so I had to do better. I found a solution that allowed me to only have to insert into the priority queue log n times with everything else remaining constant time. So, the complexity is log(n) * log(log(n)). Is that my asymptotic complexity or can this be simplified further?

Here is the alogrithm. I was able to reduce the complexity by using a hashmap to count the duplicate prioroities that would be inserted into the priority queue and providing a single calculation based on that.

I know by my code that it may not be intutitve how n log n complexity is reduced to log n log log n. I had to walk through examples to figure out it n was reduced to log n. While solvedUpTo used to increase at the same rate as n, now by ~n<=20 there were half the steps to get to the same value in solvedUpTo, ~n<=30 there were 1/3 the steps, quickly after that it was at 1/4 the steps and so on (all approximates, because I cannot remember the exact numbers).

The code is intentionally left ambiguous to what it is solving:

fun  solve(n:Long, x:Long, y:Long): Long {

    val numCount = mutableMapOf<Long,Long>()

    val minQue: PriorityQueue<Long> = PriorityQueue<Long>()

    addToQueue(numCount,minQue,x,1)
    addToQueue(numCount,minQue,y,1)

    var answer = x + y

    var solvedUpTo = 2L

    while (solvedUpTo < n) {

        val next = minQue.poll()

        val nextCount = numCount.remove(next)!!

        val quantityToSolveFor = min(nextCount,n - solvedUpTo)

        answer = ((answer + ((next + x + y) * quantityToSolveFor))).rem(1000000007)

        addToQueue(numCount,minQue,next + x,quantityToSolveFor)
        addToQueue(numCount,minQue,next + y,quantityToSolveFor)

        solvedUpTo += quantityToSolveFor
    }

    return answer
}

fun <K> addToQueue(numCount: MutableMap<K,Long>, minQue: PriorityQueue<K>, num: K, incrementBy: Long) {

    if (incrementMapAndCheckIfNew(numCount, num, incrementBy)) {
        minQue.add(num)
    }
}

//Returns true if just added
fun <K> incrementMapAndCheckIfNew(map: MutableMap<K,Long>, key: K, incrementBy: Long): Boolean {

    val prevKey = map.putIfAbsent(key,0L)

    map[key] = map[key]!! + incrementBy

    return prevKey == null
}

Answer 1

Nope, O(log n log log n) is as simplified as that expression is going to get. You sometimes see runtimes like O(n log n log log n) popping up in number theory contexts, and there aren’t simpler common functions that quantities like these are equivalent to.