Big-Oh Basics 2 - Single Loops

Computer Science Level 1

What is the runtime of the following function?

function f(n)
    k = 0
    for i in 1 to n:
         k := k * i
    return k

O(n^3)

O(n)

O(n^2)

O(1)

1 solution

Spencer Whitehead
Feb 26, 2016

Notice that we have an inner for loop that runs $n$ times. So if we double $n$ , we double the amount of time spent in that for loop. In general, the time the function takes to run is proportional to $n$ , so we say that $f(n) \in O(n)$

Big-Oh Basics 2 - Single Loops

1 solution

0 pending reports