-3

Please consider the following algorithm -

for( j = 1; j < n ; j = j * 3)
{
    for( k = 1 ; k <= n ; k = k + 2 )
    {
      r = i + j + k ;

    System.out.println(r);
    }
}

How is the time and space complexity found for this?

Arun E.R
  • 21
  • 1
  • 8
  • The time complexity is O(n^2), for space you have O(1) – Aris Oct 23 '21 at 08:00
  • 1
    Does this answer your question? [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Saurabh Dhage Oct 23 '21 at 08:04

1 Answers1

1

The outer loop will have log3 n iterations, the inner loop will have n / 2 iterations (2 is a constant and can be ignored), thus time complexity is O(N log N).

The space complexity is O(1) because no arrays/lists is created here with regard to N.

Nowhere Man
  • 19,170
  • 9
  • 17
  • 42