What will be the time complexity of this algorithm

I am very new to competitive programming and to Big O notation.

public void function(int n){
   for(int i = n; i > 0; i/=3){
       for(int j = 0; j < i; j++){
           System.out.println("Hello");
       }
   }
}

This is the algorithm.
As far as i know about time complexity.It defines how run time gets affected from number of inputs.

So here if we take a example
if 'n' is 10.
The outer loop runs log n times and the inner loop runs 'i' times.

the inner loop runs relatively to 'i' not 'n'.
So im a bit confused here as to how the time complexity is calculated.
I think it is O(log n).Please correct me if i am wrong.

Will it be O(log n) or O (n log n) or (n^2).
Please help me out with this.
Thank you.

I will try to explain it in the simplest term possible

The outer loop will simply run log(n) with base 3 times.

Since, i is decreasing by factor of 3 every time. The total work done is equal to :

n + n/3 + n/9 + n/27 + .... n/(3^log(n))

since, n/3 + ... + n/(3^log(n)) will always be less than n

for e.g. let n = 100
then, 100 + 100/3 + 100/9 + 100/27 + ... = 100 + (33.3 + 11.11 + 3.7 + ...)

we can clearly see the terms in the bracket will always be less than 100

The total time complexity of the overall solution will be O(n).

Actually it will never terminate cause i=0 and update is i *= 3 so i will stay 0 so we can say O(+oo)

assuming you meant for(int i =1... instead, then its O(n):

• Outer loop is clearly O(log_3 n) cause we keep multiplying by 3
• Inner loop will get executed O(log_3 n) times with iteration count of (1 + 3 + 9 + 27 + ... + 3^log_3(n)) which is clearly a geometric progression, solving which gives us approx 3^log_3(n)) which according to log rules gives n so this loop takes O(n) for all iterations, so total complexity is O(n)

for your code :

for(int i = n; i > 0; i/=3){
   for(int j = 0; j < i; j++){
       System.out.println("Hello");
   }

}

Inner loop variable j is dependent on outer loop variable i, so your inner loop will be the one which will decide the complexity for your algorithm.
since j will run 'n' times in first run, 'n/3' times in second run and so on.. therefore your total complexity can be calculated as

n + n/3 + n/9 + n/27 + .......

resulting in O(n)

So this is a great question! It's a tricky one that takes a little more thinking to analyse.

As correctly stated in some of the other answers, the outer loop:

for(int i = n; i > 0; i/=3)

Will run log(n) times. Specifically log_3(n) times but in big O notation we don't often worry about the base so log(n) will be fine.

Now the nested loop is a bit trickier:

for(int j = 0; j < i; j++){

On first glance you may think this is a simple log(n) loop but lets look a little further.
So on the first iteration this will run N times since the value of i will be n. Next iteration it will be run n/3 times. Then n/9, n/27, n/81 etc....

If we sum this series, it is clear to see it will total less than 2n.
Therefore we can conclude this algorithm has a complexity of O(n).

In your code snippet:

for (int i=0; i < n; i*=3) { 
    for (int j=0; j < i; j++) {
        System.out.println("Hello");
    }
}

The outer loop in i is O(log_3(n)), because each increment of the loop decreases the amount of ground needed for i to reach n by a factor of 3. This is logarithmic behavior (log_3 in this case). The inner loop in j simply iterates the same number of times as whatever the outer value of i might be, so we can just square the outer complexity, to arrive at:

O(log_3(n)^2)