Skip to content
Ultimate Algorithm

Time Complexity

What is Time Complexity?

Time Complexity is computational complexity that describes the amount of computer time it takes to run an algorithm

Here are some examples of time complexity

Question 1
nums = [1, 2, 3, 4, 5]
for n in nums:
    print(n)
Answer
O(N)
The code runtime depends on length of nums. As the nums gets bigger, the run time only gets bigger in linear time O(N)

Question 2
nums = [1, 2, 3, 4, 5]

for n1 in nums:
    for n2 in nums:
        print(n1, n2)
Answer
O(N^2)
The code runtime depends on length of nums. As the nums gets bigger, the run time gets bigger by N^2 because of the nested loop

Amortized vs Averaged Runtime?

  • Averaged is often used when the case is random(unpredictable).

  • Amortized is often used when the case is predictable but is too good to just diminish all the runtime performance just because of some slow cases(predictable).

  • From: Amortized vs Averaged runtime https://gist.github.com/jconnolly/5acf05f279a7e9e40371