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))
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))