Please consider the following code fragments (a), (b), (c) and (d) where n is the variable specifying data size and C is a constant. What is the tight bound big-Oh time complexity in terms of n in each case? Show all necessary steps. (a) for (int i = 0; i < n; i = i + 10) ---------for (int j = 1; j < 1024; j = j*2) ---------------Sum[i] += j * Sum[i]; b) for (int i = 1; i < n; i = i*2) ---------for (int j = 0; j < i; j = j+2) ---------------Sum[i] += j * Sum[i]; c)for (int i = 1; i < n; i = i * 2) --------for (int j = 1; j < i; j = j * 2) -------------Sum[i] += j * Sum[i]; d)for (int i = 0; i < n; i++) --------for (int j = 1; j < n; j *= C) ------------- Sum[i] += j * Sum[i]; (
Please consider the following code fragments (a), (b), (c) and (d) where n is the variable specifying data size and C is a constant. What is the tight bound big-Oh time complexity in terms of n in each case? Show
all necessary steps.
(a) for (int i = 0; i < n; i = i + 10)
---------for (int j = 1; j < 1024; j = j*2)
---------------Sum[i] += j * Sum[i];
b) for (int i = 1; i < n; i = i*2)
---------for (int j = 0; j < i; j = j+2)
---------------Sum[i] += j * Sum[i];
c)for (int i = 1; i < n; i = i * 2)
--------for (int j = 1; j < i; j = j * 2)
-------------Sum[i] += j * Sum[i];
d)for (int i = 0; i < n; i++)
--------for (int j = 1; j < n; j *= C)
------------- Sum[i] += j * Sum[i];
(I USED THE DASHED LINES BECAUSE IT WASN'T ALLOWING ME TO SUBMIT WITH EXTRA SPACES. SO, CONSIDER THE DASHED LINES AS SPACES/TABS)
Step by step
Solved in 6 steps with 7 images
