3
$\begingroup$

Sorry for the perhaps basic question, but my time at university is long ago and I need to brush up on Big-O stuff for interviews.

My question is, what would the time complexity be when an algorithm does depend on the input but not on the size of the input? For example, assume I have this function:

func doSomething(numbers []int) int {
    // find maximum number
    maxNumber := max(numbers)
    for i := 0; i < maxNumber; i++ {
      // magic happens here
    }
}

func maxNumber(numbers []int) (max int) {
     for _,num := range numbers {
           if num > max {
              max = num
            }
     }
     return max
}

How would you define the Time-Complexity of doSomething? The amount of iterations happens to be the maximum number in the input, so if the input is [1000000] we get 1000000 iterations with input size 1. Yet if the input would be [1,1,1,1,1,....] the iteration would still only be 1 even though our input size would be much greater.

Of course the maxNumber would be O(n) but my understanding is that you would ignore this in the calculation of doSomething.

I could say O(1) because it's not dependent of the input size, but that seems wrong to me because different input could have different iterations.

$\endgroup$
1
$\begingroup$

The time complexity of doSomething is $O(\max(n,m))$, where $n$ is the length of the input, and $m$ is the maximum number in the input. The letter $m$ is not standard – you can use a different one if you prefer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.