I need a clear-cut understanding. We know a constant-time method is O(1) and a linear-time method is O(N). Please briefly explain type-1 and type-2, and what is the difference. And why type-1, and type-2 will go O(1), and O(N) respectively. Thanks in advance.

Type-1:

func printLoop() {
    for p in 0..<100 {
        print(p)
    }
}

printLoop()

Type-2:

func printLoop(n: Int) {
    for p in 0..<n {
        print(p)
    }
}

printLoop(100)

CodePudding user response：

The difference here has to do with semantics. In fact if you pass n = 100 to the second function then both versions will take the same time to run. The first printLoop() executes a fixed number of prints, and so is said to have a constant O(1) running time. The second version loops n times, and therefore has an O(n) running time based on the input.

CodePudding user response：

Type-1 is O(1) because there is no input parameter for the method. You can't change the time it takes to complete. (If completing the function of type-1 is going to take 1 second, it is always 1 second no matter where and how you are using that.

Type-2 is O(n) because if you pass it 100, it may take 1 second to complete (As we assumed in the above section), but if you pass 200, it will take twice the time, right? It is called "linear time" because it goes up by a linear function. (Y = alpha * X where X refers to the number of loops and Y refers to the time for Type-2 function to complete its operation)