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 n?

int nthUglyNumber(int n):
  nth = 1
  for i = 1..INFINITY:
    if (isUgly(i)):
    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.

  • $\begingroup$ why the 'for' cicle runs to INFINITY? $\endgroup$ – Yamar69 Dec 2 '19 at 9:25
  • $\begingroup$ because this is a theoretical question where i put aside the fact that in the real world integers are bound to some maximum number such as 2^64. $\endgroup$ – lolski Dec 4 '19 at 8:46

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.