Big-O notation for the given function whose runtime complexity grows faster than the input

Question

I struggle to determine the runtime complexity of a function I thought of while trying to solve this LeetCode quiz. The quiz itself goes like this:

Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 are the first 11 ugly numbers (n=1 up to n=11). On the other hand, 14 does not classify as an ugly number because it has the factors of 2 and 7. The same goes for 33, which has factors of 3 and 11.

If hypothetically, I come up with a function isUgly(i) which can determine whether a given number classifies as an ugly number in O(1) time, I can just brute-force it by testing for every number from 1 to infinity. What would be the algorithmic complexity of such implementation the with respect to the value of n?

int nthUglyNumber(int n):
  nth = 1
  for i = 1..INFINITY:
    if (isUgly(i)):
      nth++;
    if (nth == n):
      return nth;

boolean isUgly(int i):
  # a function that runs in O(1) time that can determine
  # whether a number classifies as an ugly number by returning true / false

The function will return 12 for n=10, and 1536 for n=100 and based on our brute force implementation the function has to iterate 12 and 1536 times to come up with those answers.

We can generalise that if the function returns x for some n, it will have to iterate x times. Therefore, is it acceptable to conclude that this function runs in O(fn(n)) time?

NOTE: There exist a more efficient solution to the problem but that is not what I'm interested in. I am here to understand how to describe the algorithmic complexity of the definition above.

Answer 1

Yes, if you write a loop like that, and $u(n)$ is the $n$th ugly number, your runtime will be $O(u(n))$.

Answer 2

If you express the runtime relative to the input value, it is O(f(n)). But often we describe the runtime relative to the input size; for k bit input it is $O(f(2^k-1))$.

Now I guess the m-th ugly number is greater than $2^{m^{1/3}}$, so this grows quite quickly. It would grow so fast that divisibility by 2,3 and 5 only cannot be checked in constant time.

Since others will be interested in an efficient solution: an ugly number is either 1 or a smaller ugly number multiplied by 2, 3 or 5. Algorithm:

Create a priority queue q. 
Add 1 to the queue q. 
For k = 1 to m
    Extract the smallest number u from the queue q. 
    u is the k-th ugly number. 
    Add 2u, 3u and 5u to the queue q. 

This takes O(m log m) time And O(m) space. Time and space can be greatly reduced by finding a good lower and upper bound for u(m), counting the ugly numbers less than the upper bound in a double loop, and only adding numbers less than the upper bound to the priority queue.

PS You can’t classify a number as ugly in constant time.

PPS. Finding the first n ugly numbers can be done in O(n) operations except that the numbers involved might get large by merging arrays 2k, 3k and 5k in some range. Finding the n-th ugly number might be possible faster than O(n), but that’s tricky.