CODEWITHSUNDEEP
time-complexity
andrei4georgescu
andrei4georgescu

Reputation: 13

Is this O(N) algorithm actually O(logN)?

I have an integer, N. I denote f[i] = number of appearances of the digit i in N. Now, I have the following algorithm.

FOR i = 0 TO 9 FOR j = 1 TO f[i] k = k*10 + i;

My teacher said this is O(N). It seems to me more like a O(logN) algorithm. Am I missing something?

Upvotes: 1

Views: 77

Answers (3)

Scratte
Scratte

Reputation: 3166

I find your explanation a bit confusing, but lets assume N = 9075936782959 is an integer. Then O(N) doesn't really make sense. O(length of N) makes more sense. I'll use n for the length of N.

Then f(i) = iterate over each number in N and sum to find how many times i is in N, that makes O(f(i)) = n (it's linear). I'm assuming f(i) is a function, not an array.

Your algorithm loops at most:

  • 10 times (first loop)
    • 0 to n times, but the total is n (the sum of f(i) for all digits must be n)

It's tempting to say that algorithm is then O(algo) = 10 + n*f(i) = n^2 (removing the constant), but f(i) is only calculated 10 times, each time the second loops is entered, so O(algo) = 10 + n + 10*f(i) = 10 + 11n = n. If f(i) is an array, it's constant time.

I'm sure I didn't see the problem the same way as you. I'm still a little confused about the definition in your question. How did you come up with log(n)?

Upvotes: 0

kaya3
kaya3

Reputation: 51037

The time complexity of an algorithm is generally measured as a function of the input size. Your algorithm doesn't take N as an input; the input seems to be the array f. There is another variable named k which your code doesn't declare, but I assume that's an oversight and you meant to initialise e.g. k = 0 before the first loop, so that k is not an input to the algorithm.

The outer loop runs 10 times, and the inner loop runs f[i] times for each i. Therefore the total number of iterations of the inner loop equals the sum of the numbers in the array f. So the complexity could be written as O(sum(f)) or O(Σf) where Σ is the mathematical symbol for summation.

Since you defined that N is an integer which f counts the digits of, it is in fact possible to prove that O(Σf) is the same thing as O(log N), so long as N must be a positive integer. This is because Σf equals how many digits the number N has, which is approximately (log N) / (log 10). So by your definition of N, you are correct.

My guess is that your teacher disagrees with you because they think N means something else. If your teacher defines N = Σf then the complexity would be O(N). Or perhaps your teacher made a genuine mistake; that is not impossible. But the first thing to do is make sure you agree on the meaning of N.

Upvotes: 1

Eric
Eric

Reputation: 11662

I think that you and your teacher are saying the same thing but it gets confused because the integer you are using is named N but it is also common to refer to an algorithm that is linear in the size of its input as O(N). N is getting overloaded as the specific name and the generic figure of speech.

Suppose we say instead that your number is Z and its digits are counted in the array d and then their frequencies are in f. For example, we could have:

   Z = 12321
   d = [1,2,3,2,1]
   f = [0,2,2,1,0,0,0,0,0,0]

Then the cost of going through all the digits in d and computing the count for each will be O( size(d) ) = O( log (Z) ). This is basically what your second loop is doing in reverse, it's executing one time for each occurence of each digits. So you are right that there is something logarithmic going on here -- the number of digits of Z is logarithmic in the size of Z. But your teacher is also right that there is something linear going on here -- counting those digits is linear in the number of digits.

Upvotes: 1

Related Questions