PDA

View Full Version : Time complexity of algorithms



Harry Hunt
13-05-2004, 12:53 PM
This is a little quiz...

What's the uniform time complexity of the following algorithms?

1) Very simple

function DoSomething1(S: string): string;
begin
Result := S + 'Hello World';
end;

a) O(1)
b) O(n)
c) O(n<sup>2</sup>)


2) Still quite simple

function DoSomething2(S: string): string;
var
I: Integer;
begin
Result := S;
for I := 1 to Length(S) do
Result := Result + 'Hello World';
end;

a) O(1)
b) O(n)
c) O(n<sup>2</sup>)


3) A bit harder

function DoSomething3(X: Integer): Integer;
var
I: Integer;
begin
I := 1;
while I * I <= X do
I := I + 1;
Result := I - 1;
end;

a) O(1)
b) O(n)
c) O(n<sup>2</sup>)

4) Hard

function DoSomething4(N: Integer): Integer;
var
Sum, I, J, K: Integer;
begin
Sum := 0;
for I := 1 to N do
for J := 1 to (N div I) do
for J := 1 to N do
Sum := Sum + K;
Result := Sum;
end;

a) O(n<sup>3</sup>)
b) O(n<sup>2</sup> log(n))
c) O(n log<sup>2</sup> (n))
d) O(n log(n))

cairnswm
14-05-2004, 09:21 AM
My answers

1 - a
2 - b
3 - c
4 - b

Harry Hunt
14-05-2004, 11:08 AM
Almost right.
3) takes sqrt(n) steps to complete and that's in O(n)

For everybody who hasn't heard of O-Notation before...
From a mathematical point of view, it's a way to describe how something develops or grows.
When programming, O-Notation can be used to describe both the time- and space complexity of an algorithm.
Of course you could check how long an algorithm takes to complete with a stop watch (or by implementing something similar into your code), but that would give you a result that depends on the speed of your computer.
With O-Notation, the only "factor" in the equation is the length of the input value.

Algorithm 1) (see above) completes in one step and that step is independent from the input length. That's why it's in O(1) which is also called "constant time complexity". If it completed in 100 steps, it would also be in O(1) if those steps were independent from the length of the input word.

In algorithm 2) there is a for-loop that goes through the entire length of the input string. If the length of that string is "n", then the time complexity is in O(n). This is also called "linear time complexity".

In algorithm 2) the input length is the value of "x". Since the program calculates the integer-sqrt of the number x, it takes sqrt(x) steps to complete. The execution time depends on the length of x and even though sqrt(x) is < x, it's still in O(n) (because you don't normally write O(sqrt(n)).

In algorithm 3) you have two for-loops from 1 to N that are nested, so that already gives you n<sup>2</sup>. The second for loop from 2 to (N div I) takes <= log(n) steps to complete and since all three loops are nested, you get O(n<sup>2</sup>log(n)).

O-Notation is very useful for comparing algorithms, for example when comparing sorting algorithms.
Thought I'd share this with you... :lol:

cairnswm
14-05-2004, 11:14 AM
Last time I found this usefull was at university 12 years ago :)

Since then its been - which is fastest - if neccessary test two ways on the same machine and decide :)