-3

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)
AMIT
  • 906
  • 1
  • 8
  • 20
  • 1
    How much work happens in type 1? How much in type 2? How does the amount of work type 2 does change as `n` changes? How does the amount of work in type 1 change? – Stephen Newell Oct 18 '22 at 03:30
  • Does this answer your question? [How can I find the time complexity of an algorithm?](https://stackoverflow.com/questions/11032015/how-can-i-find-the-time-complexity-of-an-algorithm) – Welbog Oct 18 '22 at 12:56

2 Answers2

2

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.

Tim Biegeleisen
  • 502,043
  • 27
  • 286
  • 360
2

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)

Amirhossein Sefati
  • 656
  • 5
  • 12