I struggle to determine the runtime complexity of a function I thought of while trying to solve this 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
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.