title: Big O of Ugly Numbers Algorithm (Brute force method)
body: <p>Link to problem: <a href="https://www.geeksforgeeks.org/ugly-numbers/" rel="nofollow noreferrer">Ugly Numbers</a></p>
  
  <p>How would you find the Big O of the brute force (Simple Method Approach) solution for Ugly-Numbers.</p>
  
  <p>I see that for this part of the code:</p>
  
  <pre><code>    /* Function to check if a number is ugly or not */
  int isUgly(int no) 
  { 
    no = maxDivide(no, 2); 
    no = maxDivide(no, 3); 
    no = maxDivide(no, 5); 
  
    return (no == 1)? 1 : 0; 
  }     
  </code></pre>
  
  <p>Each step takes <code>log_2(x) + log_3(x) + log_5(x)</code> steps, where <code>x = no</code></p>
  
  <p>So this would mean the runtime is <strong>(log_2(x) + log_3(x) + log_5(x))<sup>n</sup></strong> where x is the result of the output. However, the result of an algorithm can't be a part of the Big O notation right? If it can't, this would be reduced to <strong>c<sup>n</sup></strong> right? Where <strong>c > result</strong>. What is the proper method of proof for this?</p>