Time complexity of algorithms

[Harry Hunt]

This is a little quiz...

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

1) Very simple
[pascal]
function DoSomething1(S: string): string;
begin
Result := S + 'Hello World';
end;
[/pascal]
a) O(1)
b) O(n)
c) O(n²)


2) Still quite simple
[pascal]
function DoSomething2(S: string): string;
var
I: Integer;
begin
Result := S;
for I := 1 to Length(S) do
Result := Result + 'Hello World';
end;
[/pascal]
a) O(1)
b) O(n)
c) O(n²)


3) A bit harder
[pascal]
function DoSomething3(X: Integer): Integer;
var
I: Integer;
begin
I := 1;
while I * I <= X do
I := I + 1;
Result := I - 1;
end;
[/pascal]
a) O(1)
b) O(n)
c) O(n²)

4) Hard
[pascal]
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;
[/pascal]
a) O(n³)
b) O(n² log(n))
c) O(n log² (n))
d) O(n log(n))