How to calculate the time complexity of this code

Question

I have to calculate the time complexity of the code below using the Big-O notation. I got O(nlogn) as an answer.

Input/output statements O(1)
Inner loop O(n) because the it will output 1,2,4,8,..x (2^0 +2^1 + 2^2..2^x)
Outer loop O(logn)
The statements inside the outer loop logn (n)

T(n) = O(1) + O(nlogn) = O(nlogn)

But I am not sure. Can someone help me, please.

Scanner sc = new Scanner(System.in);
System.out.print("Enter a number:");
int x = Integer.parseInt(sc.next());
for(int i=1 ; i<x; i*=2) {
  System.out.print("*");
  for(int j=0; j<i;j++) {
    System.out.print(" ");
  System.out.println("*");
}

refer : https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it?rq=1 — p._phidot_, Jul 05 '21 at 08:42

score 1 · Answer 1 · answered Jul 05 '21 at 08:47

1

As you found the time complexity is:

T(x) = 1 + 2 + 4 + ... + 2^{log(x)}

But you have a mistake in the result of the above summation. As T(x) is a geometric series with factor 2:

T(x) = 2^{log(x) + 1} - 1 = 2*x - 1

So, it means T(x) is in Theta(x) and also O(x).

answered Jul 05 '21 at 08:47

OmG

18,337
10
57
90

for the whole code? or only for the outer for loop? – Jake Jul 05 '21 at 09:45
@Jake Of course, It's the complexity of the whole code (outer and inner loop). – OmG Jul 05 '21 at 13:55

How to calculate the time complexity of this code

1 Answers1