Time Complexity of algorithm scaling runtime axis?

Mine output on the left in jupyter/spyder VS. Output on the right from dataquest built in compiler:


figure 1.

My Code:

import time
import random
import matplotlib.pyplot as plt

def plot_times(times):
    plt.plot(times)
    plt.ylabel('runtime')
    plt.xlabel('size')
    plt.show()

def sum_values(values):
    total = 0            
    for value in values: 
        total += value   
    return total  

def gen_input(length):
    return [random.randint(-1000, 1000) for _ in range(length)]

# add your code below
times = []
for length in range(1, 501):
    values = gen_input(length)
    start = time.time()
    sum_values(values) 
    end = time.time()
    times.append(end-start)

print(times)
plot_times(times)

What I expected to happen:
I expected same output as the one from DQ, with scaled versions of the runtime output.

What actually happened:
Instead mine outputs, in jupyter and spyder, ignored some very small values - and simply denoted them as zero’s. I assume fast cpu clock speeds does not have anything to do with the output.

edit: further investigations/details. I did indeed notice a performance difference between mine runtime on 10th generation CPU vs the runtime you guys posted on m/476 (p. 4/11). The graph on the left depicts when i run (code beneath) the maximum() function on page 3/11 vs. the right graph which you guys ran on your system.


figure 2.

At a sample size of 500 array-elements if shows a runtime difference of:
left: 0.00008 s
right: 0.0006 s

The difference testing I ran of following code both came from the compiler on your server/DQ. Which depict the graphs on figure 2.

import time
import random
import matplotlib.pyplot as plt

def maximum(values):
    answer = None
    for value in values:
        if answer == None or answer < value:
            answer = value
    return answer

def gen_input(length):
    return [random.randint(-1000, 1000) for _ in range(length)]

# add your code below
times = []
for length in range(1, 501):  
    values = gen_input(length)
    start = time.time()   
    maximum(values)        
    end = time.time()       
    runtime = end - start       
    times.append(runtime)

print(time)
plt.plot(times)

Interesting @Chirc , I am doing this course as well. But what is exactly your question? Could you please explain it to me in one or two sentences? Or is your post just an investigation.

I have also noticed that some results after that are off (probably the DQ computer has gotten faster! :slight_smile: ) But the conclusions still remain the same for the time and space complexities. Hence I don’t really mind.

I reckon it is a rhetorical as well as an investigation.

  1. first of, how to scale the y-axis so it show miniscule values? “y-lim”? So that the figure 1. actually shows a linear relation as well as the values in times-array.
  2. Is the runtime affected by CPU to the extent of left and right graphs on figure 2. (Sorry if the created topic seems abit sloppy, and with alot of edits, working on project while learning on the go.)

Well, I would not worry about it too much. I assume that you have not yet learned the intricacies of matplotlib.pyplot as you are doing the Data Engineer path only right?

Don’t worry all questions are valid. And I must say, I do not know how the DQ system works at all. But your CPU is most likely faster, so that gives you the different results. Still, I wonder why it is not giving these small values, your CPU must be really fast :wink: .

I believe your figure two is showing a linear relation. Maybe you were wondering about figure one? I believe there you have actual zero values, there is a very flat linear relation there :wink: .

In the end I would recommend not to worry about it too much, especially because this is not about time in a specific case but time as a physical Quantity. Which we can order in levels of speed. 1, N, log2(N), N**2 etc.

Hope this helps!

1 Like

Mostly doing bits and pieces, to understand algorithms in a more practical way. Preparing for an exam in Algorithms and Data structures.

Atleast on their platform I get the correct plot scaling. But would be great to be able replicate it on my own compilers. Since the values mine outputs are probably around to the 10^-6 (with the slowest runtimes show vals around 10^-5).

Yes, I was referring to figure 1 (edited)
It is all those zero values :slight_smile:

Thanks for the replies!