Complex Algorithms

Level 2

An algorithm takes a number, $N$ , and returns a list of numbers, all divisors of $N$ . You may have ideas on how to implement such a problem, but you observe the following runtimes as $N$ grows. Which of these runtimes is the best upper bound for the algorithm?

$N$	Runtime (seconds)
3	1
6	4
9	9
12	16

O(n^2)

O(1)

O(\log n)

O(n)

1 solution

Spencer Whitehead
Feb 16, 2016

Given runtimes and input sizes, the logical choice for evaluating the big-oh complexity of an algorithm is to check what occurs as the input size is changed. Let $f(x)=$ the runtime when $N=x$ . For example, we see that $f(3)=1$ , and $f(2*3)=4$ . We can hypothesize that $f(cx)=c^2 f(x)$ , and by plugging this in for every piece of data with a value of $x=3$ , we can conclude that, given the data we have available, this is a reasonable idea. Since multiplying $x$ by a constant increases $f(x)$ by the square of that constant, we can conclude that our algorithm is $O(n^2)$ .

Complex Algorithms

1 solution

0 pending reports