programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Tim Cooke
• Devaka Cooray
• Ron McLeod
• Jeanne Boyarsky
Sheriffs:
• Liutauras Vilda
• paul wheaton
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Piet Souris
• Carey Brown
• Tim Holloway
Bartenders:
• Martijn Verburg
• Frits Walraven
• Himai Minh

Determine the value of CN and time comlexity for recurrence functions

Greenhorn
Posts: 8
• Number of slices to send:
Optional 'thank-you' note:

I was trying to determine the CN and the complexity for the code above

I came to this conclusion

C1 = 1 --> the terminating condition
C(N) = 3 * 2 * C(N/2) + O(N)
= 6 C(N/2) + O(N).

I want you to check the equations that I found and help me in determining the time complexity
when I tried googling I found the master theorem but we are not allowed to use it in the exam
we are only allowed to use telescoping

Marshal
Posts: 76862
366
• Number of slices to send:
Optional 'thank-you' note:
Welcome to the Ranch

What is CN? I think you are correct that your code will run in linear time.

Saloon Keeper
Posts: 14499
325
• Number of slices to send:
Optional 'thank-you' note:
Wouldn't this be at least O(n log n)? Seeing as f() is linear, and test() is run 2log2N times?

Campbell Ritchie
Marshal
Posts: 76862
366
• Number of slices to send:
Optional 'thank-you' note:

Stephan van Hulst wrote:. . . test() is run 2log2N times?

Wouldn't that mean test runs in logarithmic time? Linear time overwhelms logarithmic time.

But I am not sure about that.

Stephan van Hulst
Saloon Keeper
Posts: 14499
325
• Number of slices to send:
Optional 'thank-you' note:
Yes, but it's performing a linear algorithm a logarithmic amount of times. That means the complexity is compounded.

It's like when you have a nested for loop: You're performing a linear operation a linear amount of times, resulting in a square complexity.

In this case, the 'f() loop' is nested in the 'recursive test() loop'.

Bartender
Posts: 689
17
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:

Stephan van Hulst wrote:. . . test() is run 2log2N times?

Wouldn't that mean test runs in logarithmic time? Linear time overwhelms logarithmic time.

But I am not sure about that.

If it is running in linear time then test(200) should be twice as complex as test(100), but I don't believe it is. But algorithm analysis is not something I've studied much so I could well be wrong.

Saloon Keeper
Posts: 5168
207
• Number of slices to send:
Optional 'thank-you' note:
These analyses can be tricky. f(N) is performed as follows:

2 * f(N/2) + 4 * f(N/4) + ....

Hmm, when in doubt, do a count. So:

Outcomes:
N C(N) C(N)/N 3 * 10log(N) + 3
1 1 1 3.00
10 43 4 6.00
100 715 7 9.00
1,000 9,631 10 12.00
10,000 141,647 14 15.00
100,000 1,721,535 17 18.00
1,000,000 19,715,519 20 21.00
10,000,000 242,815,999 24 24.00
100,000,000 2,671,413,503 27 27.00
1,000,000,000 29,714,559,999 30 30.00

So a first impression gives us C(N) / N = 3*log(N) + 3

and therefore C(N) = O(NlogN + N)

author
Posts: 23928
142
• Number of slices to send:
Optional 'thank-you' note:

Agree with Stephan (and Piet). It should be O(NlogN).

Henry

Campbell Ritchie
Marshal
Posts: 76862
366
• Number of slices to send:
Optional 'thank-you' note:

Stephan van Hulst wrote:Yes, but it's performing a linear algorithm a logarithmic amount of times. That means the complexity is compounded.
. . .

Yes, that sounds like Onlognn.

I was mistaken, sorry.

mira pareksha
Greenhorn
Posts: 8
• Number of slices to send:
Optional 'thank-you' note:
First of all thank you for the replies and the discussions
Second I was trying to solve the equations I got by telescoping
CN=6 C(N/2) + O(N).
I started by supposing the N=2^k
so
C(2^k)=6C(2^k-1)+N

then I found a relation bet k and k-1

c(2^k-1)=6(6C^k-2)+2N

then I was unfortunately stuck, not knowing what to do

Piet Souris
Saloon Keeper
Posts: 5168
207
• Number of slices to send:
Optional 'thank-you' note:
hi Mira,

well the art has become a bit very rusty to me, but the derivation is well known,
if you know the theorem in which it is proved thaat merge sort is O(NlogN).

In broad lines, we have that

C(N) = 6 * C(N / 2) + N =>

C(N) = (6^2) * C(N/4) + N + 6 * (N / 2) // this last term coming from C(N/2) = 6 * C(N / 4) + N / 2

C(N) = (6^3) * C(N/8) + N + 6 * (N / 2) + 36 * (N / 4)

...

Now, it'll take logN steps before we arrive at C(1), so we finally get the expression

C(N) = 6 ^(log N) * C(1) + N ( 1 + 3 + 3^2 + 3 ^3 + ... 3 ^log N)

6 ^ logN = (6 ^ (6logN) ) ^(1 / log 6) = N^a = N

and N(1 + 3 + ... + 3 ^ log(N)) = N log N

So, finally we arrive at

C(N) = O(N) + O(NlogN)

But for some thorough explanation, there are many Youtube films that explain it much better.

I only hope that this is what you call 'telescoping'...

Greetz,
Piet

 You’ll find me in my office. I’ll probably be drinking. And reading this tiny ad. the value of filler advertising in 2021 https://coderanch.com/t/730886/filler-advertising