ZuoTi.Pro
Question

count ← 0 for(i=n; i>0; i←⌊i/2⌋) for(j=0; j<i; j++) count = count + 1 What’s the...

count ← 0
for(i=n; i>0; i←⌊i/2⌋)

for(j=0; j<i; j++) count = count + 1

What’s the Big-Theta of the running time?

indicate your time complexity.

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1 

values of i of outer loop are n, n/2, n/4, n/8, ...
    Explanation:
    -------------
    because i value is changing by i = i* through each iteration
    so, i changes to 1, 2, 4, ..., n/4, n/2, n
inner loop iterates i times.

to find total number of iterations, add all values of i
all, possible values of i are 1, 2, 4, ..., n/4, n/2, n
so, total number of iterations = n+n/2+n/4+n/8+...+4+2+1
= n(1+1/2+1/4+1/8+...)
Note: 1+1/2+1/4+1/8+... <= 2
so, n(1+1/2+1/4+1/8+...) <= 2n
hence, time complexity is ?(n)
Answer: ?(n)
0 0
Add a comment
Know the answer?
Add Answer to:
count ← 0 for(i=n; i>0; i←⌊i/2⌋) for(j=0; j<i; j++) count = count + 1 What’s the...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • What is the time-complexity of the algorithm abc? Procedure abc(n: integer) s := 0 i :=1...

    What is the time-complexity of the algorithm abc? Procedure abc(n: integer) s := 0 i :=1 while i ≤ n s := s+1 i := 2*i return s consider the following algorithm: Procedure foo(n: integer) m := 1 for i := 1 to n for j :=1 to i2m:=m*1 return m c.) Find a formula that describes the number of operations the algorithm foo takes for every input n? d.)Express the running time complexity of foo using big-O/big-

  • Question 1 (25 pts) Find the running time complexity for the following code fragments. Express yo...

    Question 1 (25 pts) Find the running time complexity for the following code fragments. Express your answers using either the Big-O or Big-Θ notations, and the tightest bound possible. Justify your answers. for(int count O , i -0; i < n* n; i++) for(int i0 ; j <i; j++) count++ for(int count O , i -0; i

  • #9 What is time complexity of fun()? int fun(int n) {   int count = 0;   for...

    #9 What is time complexity of fun()? int fun(int n) {   int count = 0;   for (int i = n; i > 0; i /= 2)      for (int j = 0; j < i; j++)         count += 1;   return count; } Group of answer choices O(n^2) O(nLogn) O(n) O(nLognLogn)

  • Let A = [A[1], A[2],…..,A[n]] be an array of n distinct integers. For 1 <= j...

    Let A = [A[1], A[2],…..,A[n]] be an array of n distinct integers. For 1 <= j <= n, the index j is a happy index if A[i] < A[j] for all 1 <= i < j. Describe an O(n)- time algorithm that finds all the happy indices in the array A. Partial credit will be given for an O(n log(n))-time algorithm and a minimal credit will be given for an O(n^2) –time algorithm. What is the running time of your...

  • Show your work Count the number of operations and the big-O time complexity in the worst-case...

    Show your work Count the number of operations and the big-O time complexity in the worst-case and best-case for the following code int small for ( i n t i = 0 ; i < n ; i ++) { i f ( a [ i ] < a [ 0 ] ) { small = a [ i ] ; } } Show Work Calculate the Big-O time complexity for the following code and explain your answer by showing...

  • 1- Find the time complexity of the following program, where n is given as input: i...

    1- Find the time complexity of the following program, where n is given as input: i = n; while (i > 1) { j = i; while (j < n) { k = 0; while (k < n) { k += 2; } j *= 2; } i /= 2; } Express your answer using theta notation, and explain the amount of time it takes for each loop to finish.

  • What is the big o cost of this method? int count = 0; int i =...

    What is the big o cost of this method? int count = 0; int i = 1; while(i < n){ for (j = 1; j < n*n; j *= n) { count++; } i *= 2; } System.out.println(count);

  • 1 question) Arrange the following in the order of their growth rates, from least to greatest:...

    1 question) Arrange the following in the order of their growth rates, from least to greatest: (5 pts) n3                     n2         nn        lg n     n!       n lg n              2n                     n 2 question)Show that 3n3 + n2 is big-Oh of n3. You can use either the definition of big-Oh (formal) or the limit approach. Show your work! (5 pts.) 3 question)Show that 6n2 + 20n is big-Oh of n3, but not big-Omega of n3. You can use either the definition of big-Omega...

  • C++ , Count number of steps for the following pseudocode(show work) along with calculating the time...

    C++ , Count number of steps for the following pseudocode(show work) along with calculating the time complexity(the Big O Efficiency). Thank you! def LeftToRight(char* diskTest, int size)                   if disks = 0:                            return none                   else                            numOfmoves = 0;                            for i from 0 to n-1                                     for j from 0 to 2n-1                                              if (diskTest[j] is 1 and diskTest [j+1] is 0)                                                       swap (disk[j] and disk[j+1])                                                       increment moves...

  • Q-1: Given the following code fragment, what is its Big-O running time? test = 0 for...

    Q-1: Given the following code fragment, what is its Big-O running time? test = 0 for i in range(n):             for j in range(n):                         test= test + i *j Q-2: Given3 the following code fragment what is its Big-O running time? for i in range(n):             test=test+1 for j in range(n):             test= test - 2 Q-3: Given the following code fragment what is its Big-O running time? i = n while i > 0:             k=2+2             i...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT