run-time

[nonevent99]

Given each function below, express the function in big-O notation. If you're feeling really zealous, find the running time in big-O notation, too. If you're feeling positively exuberant, find closed form solutions, too.

 

 

function f(n) {
 if (n   return f(n/2) + 1;
}


function g(n) {
 if (n   return 10*g(n/10) + 10;
}

function h(n) {
 if (n   return h(n/2) + h(n/4);
}

function i(n) {
 if (n   return i(n-2);
}

function j(n) {
 if (n   return j(n-2) + j(n-1);
}

function k(n) {
 if (n   return k(n/2) + n * lg(n);
}

function l(n) {
 if (n   return l(n/4) + n^7;
}

[wood]

function f(n) {
 if (n   return f(n/2) + 1;
}

f(n) = O(1) + O(logN) = O(logN)

 

function g(n) {
 if (n   return 10*g(n/10) + 10;
}

g(n) = O(10^log10 N) + O([10^[(log10 N) + 1] - 1] / 9) = O(10^log10 N) = O(n)

 

I'll get to the rest later.

 

Wood

[nonevent99]

I think your answer for g is right, g(n) approx = n/5.

 

I'm not so sure about f.

 

 

[AlbaLed]

function f(n) {
 if (n   return f(n/2) + 1;
}

[color=Red]f(n) = O(log(n))[/color]

function g(n) {
 if (n   return 10*g(n/10) + 10;
}
[color=Red]g(n) = O(log(n))[/color]

function h(n) {
 if (n   return h(n/2) + h(n/4);
}

[color=Red]h(n) = O(nlog(n))[/color]

function i(n) {
 if (n   return i(n-2);
}

[color=Red]i(n) = O(n)[/color]

function j(n) {
 if (n   return j(n-2) + j(n-1);
}
[color=Red]j(n) = O(2^(n-4))[/color]

function k(n) {
 if (n   return k(n/2) + n * lg(n);
}

[color=Red]k(n) = O(log(n))[/color]

function l(n) {
 if (n   return l(n/4) + n^7;
}
[color=Red]l(n) = O(log(n))[/color]

 

I kind of doubt that you wanted those results. A more interesting problem would be what's returned by the above functions? That would be equivalent to solving some recurrence equations.

Given each function below, express the function in big-O notation. If you're feeling really zealous, find the running time in big-O notation, too., What do you mean by that, isn't big-O notation used for the time complexity of algos? What do you mean by first sentence?

[wood]

AlbaLed, can you explain your answer to this question?

 

function g(n) {
 if (n   return 10*g(n/10) + 10;
}

 

 

(1)       g(n) = 10*g(n/10)+10
(2)            = 10*(10*g(n/100)+10)+10
(3)            = 10*(10*(10*g(n/1000)+10)+10)+10
   ...
(log10(n))     = 10^(log10(n)-1) + 10^(log10(n)-1)+10^(log10(n)-2)+...+10
              = n/10 + [10^(log10(n) - 10] / 9
              = n/10 + (n - 10)/9
              = O(n)

 

Am I missing something? I double checked by running the C fragment and it looks definitely linear...

 

Thanks,

Wood

[rafi_dery]

Wood: I think AlbaLed refered to the running time of the functions.

AlbaLed: about h: why is it O(nlogn) and not O(n)?

[The_Wonderful_Vipul]

Originally posted by nonevent99

 

Given each function below, express the function in big-O notation. If you're feeling really zealous, find the running time in big-O notation, too. If you're feeling positively exuberant, find closed form solutions, too.

 

 

function f(n) {
 if (n   return f(n/2) + 1;
}

[/quote]
[color=Red]

O(log(n))

[/color]
[quote]



function g(n) {
 if (n   return 10*g(n/10) + 10;
}

[/quote]
[color=Red]

O(n)

[/color]

[quote]

function h(n) {
 if (n   return h(n/2) + h(n/4);
}

[/quote]
[color=Red]
O(lg(n)^2)
[/color]
[quote]


function i(n) {
 if (n   return i(n-2);
}

[/quote]
[color=Red]
O(n)
[/color]
[quote]

function j(n) {
 if (n   return j(n-2) + j(n-1);
}

[/quote]
[color=Red]
O(2^n)
[/color]

[quote]
function k(n) {
 if (n   return k(n/2) + n * lg(n);
}

[/quote]
[color=Red]
O(nlog(n))
[/color]
[quote]

function l(n) {
 if (n   return l(n/4) + n^7;
}

[/quote]
[color=Red]

O(n^7)
[/color]

[wood]

Originally posted by rafi_dery

 

Wood: I think AlbaLed refered to the running time of the functions.

AlbaLed: about h: why is it O(nlogn) and not O(n)?

 

Rafi: I didn't understand what you meant by that. I am also refering to the running time of the functions. What would be the other interpretation?

[wood]

function j(n) {
 if (n   return j(n-2) + j(n-1);
}
[color=Red]j(n) = O(2^(n-4))[/color]

 

That looks like fib series. However, recursion should stop at j(4) or below.

 

So, the recursion is 2^k f(n-2k) and considering n-2k = 4, k = (n-4)/2, so the recursion is O(2^[(n-4)/2]) to be precise and not 2^(n-4), right?

 

Please, let me know.

 

Wood

[AlbaLed]

[/size]Originally posted by wood

 

AlbaLed, can you explain your answer to this question?

 

function g(n) {
 if (n   return 10*g(n/10) + 10;
}

 

 

(1)       g(n) = 10*g(n/10)+10
(2)            = 10*(10*g(n/100)+10)+10
(3)            = 10*(10*(10*g(n/1000)+10)+10)+10
   ...
(log10(n))     = 10^(log10(n)-1) + 10^(log10(n)-1)+10^(log10(n)-2)+...+10
              = n/10 + [10^(log10(n) - 10] / 9
              = n/10 + (n - 10)/9
              = O(n)

 

Am I missing something? I double checked by running the C fragment and it looks definitely linear...

 

Thanks,

Wood[/size]

 

Wood you're finding what the program returns not the running time, big-O, that's why I said it could have be good if the quest asked for what's returned too.

[wood]

Ops... got it... stupid mistake.

 

Wood

[AlbaLed]

rafi_dery, thanks for pointing it out, I think you're right

Here is the idea

 

h(n) = h(n/2) + h(n/4)

 

so the value & complexity of this function should be the number of leaves on a binary tree with n nodes. or

 

2^(hght-1)

hght = log(n)

2^(log(n)-1) = O(n)

 

thnx

 

[nonevent99]

Ok, guys, here are the answers I got. They augment what you all wrote above, and in at least one case contradict your answers. Maybe we can hash the differences out...

 

Given each function below, express the function in big-O notation. If you're feeling really zealous, find the running time in big-O notation, too. If you're feeling positively exuberant, find closed form solutions, too.

 

 

f(n) = f(n/2)+1

f(n) = O(lg(n)) {master theorem}

run time = O(lg(n)) {n divided by 2 per iteration}

 

g(n) = 10*g(n/10)+10

g(n) = O(n) {master theorem}

run time = O(log n) {n divided by 10 per iteration}

 

h(n) = h(n/2) + h(n/4)

h(n) = O(n) {writing them out thru n=128}

run time = O(lg n) {n dividied by at least 2 per iteration)

 

i(n) = i(n-2); i(n) = n when n

i(n) = 2 - n%2 {writing a few out}

run time = O(n) {n reduced by 2 per iteration}

 

j(n) = j(n-2) + j(n-1)

j(n) = O(phi^n) {Fibonnaci sequence}

run time = O(phi^n); phi = (1+sqrt5)/2

 

k(n) = k(n/2) + nlgn

k(n) = O(nlgn) {Master theorem}

run time = O(lg n) {n divided by 2 per iteration}

 

l(n) = l(n/4) + n^7

l(n) = O(n^7) {Master theorem}

run time = O(log n base 4) {n divided by 4 per iteration}

 

 

 

Fun?

[AlbaLed]

lots of it !!!! You've got more ??? Good job nonevent

[AlbaLed]

nonevent are you sure about h, I am getting something different for the run time, check my last post

[wood]

I agree... it should be O(n).

 

Wood

[nonevent99]

Originally posted by AlbaLed

 

nonevent are you sure about h, I am getting something different for the run time, check my last post

 

Yeah, I think the run time will be more than O(lg n) for h(n). My bad. It's definitely bounded above by 2*R(n/2), since R(n/2) > R(n/4) (R = run time), which is to say bounded above by R(n).

 

The actual R(n) = R(n/2) + R(n/4) + 1.

 

This turns out to be another situation like in the other thread http://www.TestMagic.com/forum/topic.asp?TOPIC_ID=8612 where it would be O(n) if we were doing 2*R(n/2), but since we aren't quite adding R(n/2) each time, it's still O(n^p) but p

 

In this case, it appears that a good p is 0.7. SO the runtime is O(n^p) for h.

 

This is very interesting.

 

 

 

[AlbaLed]

nonevent, if you want a really tight tight tight tight tight bound I thin you've got to be looking at n^(log4(3)) = O(n^0.79). How did you get 0.7??

[nonevent99]

Originally posted by AlbaLed

 

nonevent, if you want a really tight tight tight tight tight bound I thin you've got to be looking at n^(log4(3)) = O(n^0.79). How did you get 0.7??

 

Experimentation. I could have made a mistake. But it looks like 0.7 works.

 

Here's the code I used:

 

<br />
function R(n) {<br />
if (n <= 1) return 1;<br />
return R(n/2) + R(n/4)+1;<br />
}<br />
<br />
<br />
document.write("<table>");<br />
for (var n = 1; n < 1000000; n *= 2) {<br />
    var x = R(n);<br />
    document.write("<tr><td>"+n+" <td>"+x+" <td>"+x/Math.pow(n,0.7));<br />
}<br />
document.write("");<br />
<br />

[iamdaisy]

Ok, guys, here are the answers I got. They augment what you all wrote above, and in at least one case contradict your answers. Maybe we can hash the differences out...

 

 

 

 

f(n) = f(n/2)+1

 

f(n) = O(lg(n)) {master theorem}

run time = O(lg(n)) {n divided by 2 per iteration}

 

 

g(n) = 10*g(n/10)+10

 

g(n) = O(n) {master theorem}

run time = O(log n) {n divided by 10 per iteration}

 

 

h(n) = h(n/2) + h(n/4)

 

h(n) = O(n) {writing them out thru n=128}

run time = O(lg n) {n dividied by at least 2 per iteration)

 

 

i(n) = i(n-2); i(n) = n when n

 

i(n) = 2 - n%2 {writing a few out}

run time = O(n) {n reduced by 2 per iteration}

 

 

j(n) = j(n-2) + j(n-1)

 

j(n) = O(phi^n) {Fibonnaci sequence}

run time = O(phi^n); phi = (1+sqrt5)/2

 

 

k(n) = k(n/2) + nlgn

 

k(n) = O(nlgn) {Master theorem}

run time = O(lg n) {n divided by 2 per iteration}

 

 

l(n) = l(n/4) + n^7

 

l(n) = O(n^7) {Master theorem}

run time = O(log n base 4) {n divided by 4 per iteration}

 

 

 

 

Fun?

 

 

Why there are two different O-notations : for function and runtime??

Isnot the O-notation for a function is for it's run time resource usage and space usage?? and we generally talk about run time (as space is not much an issue)

 

Please help me as I might be loosing some serious concept..

[CalmLogic]

I'm not the best at explaining this, but, basically:

 

Run-time complexity relates to execution time.

 

Function complexity relates to the growth of a fuction ("order of growth").

 

The way I grasped this concept intuitively was just looking at examples in discrete math books, ETS sample questions, examples in this forum, etc.

[taro_curly]

The O notation is an order of growth notation. It helps you to concisely represent how fast a function will "grow" w.r.t. some input.

 

Therefore, when you say that the order of growth of a function is f(n) is O(n), what you are saying is that as n increases, f(n) will increase linearly.

 

A crude way of putting it would be, if the order of growth is O(n^2), then

f(n) is proportional to n^2

i.e. f(n) = kn^2

 

When you are talking about the order of growth of a function f, you are talking about the magnitude of the function.

 

Let us say that the time to required f for input n is given by f_t(n)

Whereas, when you are talking about the growth of the running time, you are talking about f_t grows with n.

 

Hope this makes sense...

[iamdaisy]

Calmlogic and taro_curly, thank you so much for this explanation

 

------------- :)

daisy