Advertisement
Guest User

Untitled

a guest
Sep 20th, 2019
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 0.66 KB | None | 0 0
  1. Find the number of times f() is called as a function of the input size n.
  2.  
  3. a. for (i = n; i > 1; i /= 2)
  4.         f()
  5.  
  6. b. for (i = 0; i * i < n; i++)
  7.         f()
  8.        
  9. c. for (i = 0; i < n; i++)
  10.         for (j = 0; j < 256; j++)
  11.           f()
  12.          
  13. d. for (i = 1; i <= n * n - 10; i++)
  14.         for (j = 1; j <= i; j ++)
  15.             f()
  16.  
  17. e.  for (i = 1; i <= n; i++)
  18.         for (j = 1; j <= i; j++)
  19.             for (k = 1; k <= j; k++)
  20.                 f()
  21.  
  22. f. for (i = 1; i <= n; i++)
  23.         for (j = 1; j < i; j *= 2)
  24.             f()
  25.  
  26. g. for (i = 1; i <= n; i++)
  27.         for (j = 1; j <= n; j += i)
  28.             f()
  29.  
  30. h. void compute(int n)
  31.       if (n == 0) return;
  32.       for (int i = 0; i < n; i++)
  33.           f()
  34.       compute(n/2)
  35.       compute(n/2)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement