-3

Please help me by giving the time complexity analysis of the following function.

function (n)
{
    for( i = 1 ; i <= n ; i + + )
       {
            for( j = 1 ; j <= n ; j+ = i )
                {
                   print( “*” ) ;
                }
       }
}
hasibuzzaman chowdhury
  • 59
  • 8
  • 2
    StackOverflow isn't a homework solving website. We expect some demonstration of basic knowledge or attempt at a solution. We'll help you along, but we won't give you an answer. See https://meta.stackoverflow.com/a/334823/3141234 – Alexander Sep 11 '17 at 19:23
  • 4
    I'm voting to close this question as off-topic because it's a homework question that doesn't demonstrate any attempt at a solution – Alexander Sep 11 '17 at 19:24
  • `n + n/2 + n/3 + n/4 + ...` = ? – Am_I_Helpful Sep 11 '17 at 19:24
  • 1
    As https://stackoverflow.com/help/on-topic says: "Questions asking for homework help must include a summary of the work you've done so far to solve the problem, and a description of the difficulty you are having solving it." (Also, big-O analysis in general is theoretical computer science, which has its own StackExchange site; our purview here is restricted to *practical* questions). – Charles Duffy Sep 11 '17 at 19:25
  • Thanks for the answer . I also calculated the answer is O(nlogn) as (1+1/2+1/3+1/4+....+1/k) = logn . But I was practicing this problem from this [link](https://www.amazon.in/Data-Structures-Algorithms-Made-Easy/dp/0615459811) . Here they have calculated the runtime is O(n√n) , that's why , I got confused . – hasibuzzaman chowdhury Sep 11 '17 at 19:33

1 Answers1

1

I feel it should be n + n*log(n).

  1. One cycle it's O(n);
  2. Cycle inside cycle it's O(n^2);
  3. This case it should be: n*log(n) - as (n/1 + n/2 + n/3 + … + n/n) each iteration number is reducing (in n division by n), plus n, as this is also first iteration cycle;

So, final answer is: n + n*log(n).

Checked my assumption with simple test and some numbers, looks good.

Denys
  • 1,308
  • 12
  • 13