time-complexitylanguage-agnosticbig-oconceptual

Time complexity of the following two programs?


I know that the time complexity of the following code is O(n).

n = 10
for x in range(0,n): 
    print("")

I also know that the time complexity of the following code is O(n^2):

n = 10
for x in range(0,n): 
    for y in range(0,n):
        print("")

I am having trouble determining the time complexity of the following two programs.

  1. Here, we have two individual loops. Each has a time complexity of O(n). So, should the time complexity of the whole program be O(n + n)? or something else?
# program 1
 
n = 10
for x in range(0,n): 
    print("")

for y in range(0,n): 
    print("")
  1. Here, we have two individual loops again but the first loop has a time complexity of O(n^2) and the second loop has a time complexity of O(n^3). So, should the time complexity of the whole program be O(n^2 + n^3)? or something else?
# program 2

n = 10
for x in range(0,n): 
    for y in range(0,n): 
        print("")

for a in range(0,n): 
    for b in range(0,n): 
        for c in range(0,n): 
            print("")

Solution

  • yes the complexity of your 2nd program will be O(n^2) + O(n^3). You can conclude that the complexity of your program is just O(n^3) because it is the monomial term that have the biggest power.

    The complexity of your first program is O(n) + O(n) = 2.O(n) = O(n). You are reasoning well. The complexity is O(n)