Time Complexity Lesson

Numerical Time Complexity

Time Complexity is an Estimate for how much time it takes a program to run

Time Complexity of 1:

print(1)

Time Complexity of 1:

sum1 = 50 + 72

Time Complexity of 1:

sum1 = 2 ^^ 20

Time Complexity of 2:

sum1 = 50
sum1 += 72

Time Complexity of 6:

sum1 = 1
sum1 += 1
sum1 -= 2
if sum1 == 0:
  print(1)
print(sum1)

Time Complexity of 21:

sum1 = 1            # this line ran 1 time
for i in range(10): # this line ran 10 times
  print(1)          # this line ran 10 times

Time Complexity of 311:

sum1 = 1              # this line ran 1 time
for i in range(10):   # this line ran 10 times
  for j in range(10): # this line ran 100 times
    print(1)            # this line ran 100 times
    print(2)            # this line ran 100 times

Practice Problem:
What is the Time Complexity of the Following Program

list1 = [9, 2, 2, 4, 7, 9, 11]
for listnum in range(0, len(list1)):
  minvalue = list1[listnum]
  indexnum = listnum
  for i in range(listnum, len(list1)):
    if list1[i] < minvalue:
      minvalue = list1[i]
      indexnum = i
  list1[indexnum], list1[listnum] = list1[listnum], list1[indexnum]

largestnum = list1[6]
leastnum1 = list1[0]
leastnum2 = list1[1]
othernum = largestnum - leastnum1 - leastnum2
print(leastnum1, leastnum2, othernum)

Variable Time Complexity

Variable Time Complexity Depends on Input for how much time it takes for a program to run

Time Complexity: 2n + 3 or 2n

n = int(input(''))  #ran 1 time
sum1 = 0            #ran 1 time
for i in range(n):  #ran n times
  sum1 += i         #ran n times
print(sum1)         #ran 1 time

We can represent 2n + 3 with 2n

When examing variable time complexity, we can ignore the constants. The variable parts can become huge with a big n value, making the smaller constants ignorable

Time Complexity: 2n^2 + n + 3 or 2n^2

n = int(input(''))    #ran 1 time
sum1 = 0              #ran 1 time
for i in range(n):    #ran n times
  for j in range(n):  #ran n squared times
    sum1 += i+j       #ran n squared times
print(sum1)           #ran 1 time

When examing variable time complexity, we only look at the greatest powers of the same variable. With a big n value, the smaller powers are ignorable

O notation

O notation represent how fast time complexity will grow as the inputs get larger
Basically only looking at the largest n coefficient while ignoring any constants

T(100) = O(1)
T(2n + 3) = O(n)
T(2n^2 + n + 3) = O(n^2)

not all instructions take 1 time complexity, instructions like "in" takes n time complexities