Define the Time Complexity for the algorithm (Java)

Question

I have the following snippet of code:

public static int digPow(int n, int p) {
  int powCounter = p;
  int sum = 0;
  char[] digits = (""+n).toCharArray();

  for (char digit : digits) {
    sum += Math.pow(Character.getNumericValue(digit), powCounter);
    powCounter++;
  }

  if (sum % n == 0) return sum / n;
  else return -1;
}

I don't understand how to define the time complexity, because, even though I have a loop, it seems to me that it's not just O(n). Or it is?

it seems to me that it's not just O(n) why do you think so? — Sotirios Delimanolis
– Sotirios Delimanolis, Commented Dec 3, 2022 at 15:02
It's O(log n), assuming Math.pow runs in O(1) time. I'd look carefully at your accuracy though -- you return a long (suggesting the result might not fit in an int), but sum is an int, and Math.pow takes doubles (which represent all int values exactly, but not all long values). — Paul Hankin
– Paul Hankin, Commented Dec 3, 2022 at 15:31

Kaushal · Accepted Answer · 2022-12-03 14:30:28Z

1

Its O(n), where n is the length of the character array digits. Since the loop will iterate that no of times the next line is a if else clause which will execute only once.

answered Dec 3, 2022 at 14:30

Kaushal

695 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Berthur Over a year ago

Ambiguous though, since a variable n is already present in the code with a different value.

Collectives™ on Stack Overflow

Define the Time Complexity for the algorithm (Java)

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related