• Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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

Henry
 
Campbell Ritchie
Marshal
Posts: 76862
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Your help is appreciated
 
Piet Souris
Saloon Keeper
Posts: 5168
207
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
reply
    Bookmark Topic Watch Topic
  • New Topic