Solved

RunTime Complexity

Posted on 2007-04-09
21
1,353 Views
Last Modified: 2008-02-01
Hi there Buddies.
I've already answered the first 2 Functions But I wanna know if my answers are true
But I couldnt find a solution for the 3rd function
Here is the Question
1. Let n=2k , Determine RunTime Complexity for each of the following 3 functions as a function of k.
2. Calculate  prod as function of k in each case.

static int F1(int n)
            {
                  int prod=1;
                  while (n>1)
                  {
                        prod = prod *n;
                        n=n/2;
                  }
                  return prod;
            }

static int F2(int n)
            {
                  int prod=1; int m;
                  while (n>1)
                  {
                        m=n;
                        while (m>1)
                        {
                              prod = prod *2;
                              m=m/2;
                        }
                        n=n/2;
                  }
                  return prod;
            }

static double F3(int n)
            {
                  double prod=1; int x=0;
                  for (int i=1; i<=n; i++)
                        for (int j=1; j<=n*n; j++)
                              if ((j % Math.Sqrt(n))==0)
                                    for (int m=1; m<=j; m++)
                                          prod=prod *2;
                  return prod;
            }



My answers for the first 2 Functions

First Function :
Complexity as a function of n is log2(n)
Complexity as a function of k is log2(2k) = k   ,,, so It’s O(k)
Prod = 2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21  = 2k  -  2
Second Function :
Complexity as a function of n  is n*log(n)
Complexity as a function of 2k is 2k*log(2k)  = 2k * k  ,,, so It’s O(2k)
Prod =  2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21   = 2k  -  2


Thanks
0
Comment
Question by:nikorba
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 7
  • 6
  • 4
  • +2
21 Comments
 
LVL 84

Assisted Solution

by:ozo
ozo earned 60 total points
ID: 18880441
I gather that 2k means 2^k or 2**k

> Second Function :
> Complexity as a function of n  is n*log(n)
I don't think that's right
0
 
LVL 84

Expert Comment

by:ozo
ID: 18880446
> if ((j % Math.Sqrt(n))==0)
How many times would this be true?
0
 
LVL 84

Expert Comment

by:ozo
ID: 18880722
> Prod = 2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21  = 2k  -  2
Are you saying Prod is less than 2k?
0
Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 12

Expert Comment

by:Sinoj Sebastian
ID: 18880988
Sorry, not an answer, just a point

log2(2k) = 1+log2(k)  {not k; log2(2^k)=k}
0
 
LVL 2

Author Comment

by:nikorba
ID: 18883037
Hi there ,,, well , there are some mistakes in the Question ,,, because I copied it from the word Document ,,, so I thought that the exponent will appear correctly ...I will fix it now
Here is the Question
1. Let n=2^k , Determine RunTime Complexity for each of the following 3 functions as a function of k.
2. Calculate  prod as function of k in each case.

static int F1(int n)
            {
                  int prod=1;
                  while (n>1)
                  {
                        prod = prod *n;
                        n=n/2;
                  }
                  return prod;
            }

static int F2(int n)
            {
                  int prod=1; int m;
                  while (n>1)
                  {
                        m=n;
                        while (m>1)
                        {
                              prod = prod *2;
                              m=m/2;
                        }
                        n=n/2;
                  }
                  return prod;
            }

static double F3(int n)
            {
                  double prod=1; int x=0;
                  for (int i=1; i<=n; i++)
                        for (int j=1; j<=n*n; j++)
                              if ((j % Math.Sqrt(n))==0)
                                    for (int m=1; m<=j; m++)
                                          prod=prod *2;
                  return prod;
            }



My answers for the first 2 Functions

First Function :
Complexity as a function of n is log2(n)
Complexity as a function of k is log2(2^k) = k   ,,, so It’s O(k)
Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2
Second Function :
Complexity as a function of n  is n*log(n)
Complexity as a function of k is 2^k*log(2^k)  = (2^k )* k  ,,, so It’s O(2^k)
Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2

Thanks
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 65 total points
ID: 18883314
>> Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2

Not really (as ozo already noted).

           2^(k(k + 1)/2)

is more like it ... can you explain why ?


>> Complexity as a function of n  is n*log(n)

That's not correct ... you have nested loops of the same type as in the first function ... what does that give complexity wise ?
0
 
LVL 2

Author Comment

by:nikorba
ID: 18949023
OZo didn't saw my 2nd comment :)
I think the 1st two functions are correct
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 18949165
>> I think the 1st two functions are correct

No, see my previous post ...
0
 
LVL 2

Author Comment

by:nikorba
ID: 18949207
>>>No, see my previous post ...

I saw it,,,
try to solve it numerically
try a number with the F1
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 18949219
>> try to solve it numerically
>> try a number with the F1

What do you mean ?

You said :

      Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2

And that's simply not true ... (see my earlier post)
0
 
LVL 84

Expert Comment

by:ozo
ID: 19170896
there were answers
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 19170973
I agree ... nikorba apparently didn't believe us when we pointed out his mistakes ...
0
 
LVL 2

Author Comment

by:nikorba
ID: 19172044
I still think that my answers were right ,,, that;s it
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 19172171
Then I wonder why you were asking our help, if you can't accept what we have to say ?
0
 
LVL 2

Author Comment

by:nikorba
ID: 19172206
I appreciate ur help ,,, at first I wasnt sure about my answers so I asked u
but after a while the I asked the lecturer and he said my answers were right
I really thank u so much for ur help but that what happened
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 19172373
If your teacher says that this :

    Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2

is correct, then he's wrong :)

2^(k)  -  2 is smaller than 2^(k), while Prod is a lot larger. How can those two be equal ?

Try filling in k=3 for example. You say that :

    Prod = 2^3 * 2^(2) * 2^(1)  = 2^(3)  -  2
    Prod = 2^6  = 2^3  -  2
    Prod = 64  = 6

How can 64 be equal to 6 ???
0
 
LVL 20

Expert Comment

by:Venabili
ID: 19180227
OK - this is one of these "why the hell I recommended delete" :)

So what we do with the question?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 19186139
If nikorba still wants our help, then I'll be glad to provide that ... if not, then this question can be PAQ'd for ozo as he was first :)
0
 
LVL 2

Author Comment

by:nikorba
ID: 19276885
I'm sorry I discovered that I was wrong
sorry everyone :)
0

Featured Post

[Webinar] Code, Load, and Grow

Managing multiple websites, servers, applications, and security on a daily basis? Join us for a webinar on May 25th to learn how to simplify administration and management of virtual hosts for IT admins, create a secure environment, and deploy code more effectively and frequently.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses

751 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question