MCQs about Time and Space Complexity Of a Program

tutorial
21

1 B
2 C
3 B
4 B
5 C
6 D
7 C
8 D
9 C
Three Loops are there so for single loop complexity will be “n” for three loop complexity will be “n^3”
10 B
11 A
12 C
13 C
14 B
15 C
16 B
17 B
18 D
19 B
20 B
21 C

22

As both n and m are the input parameters of the function. So, we should give \mathcal{O}(n + m) as time complexity.

1 Like
23

kudos, I think all your answers are correct :slight_smile:

24

Really?
I guessed 2nd and 15th. :smiley:

25

yes, they are right too.

26

@akash_321: Yes, you are right. It will be \mathcal{O}(n).

1 Like
27

Since counter increases by 1, of course, it is expected to be O(N) worst case.

1 Like
28

So if number of occurrences of x are m then complexity will be O(m).

1 Like
29

Yes. The main focus was, it takes O(LogN) time to find ocurrances of x in the sorted array. I think this question goes by an assumption that “Number of occurances of x very less than Number of elements in array.”

3 Likes
30

Yes, You are absolutely right @akash_321, Though there exist a better way to count number of occurance of an element in a sorted array in O(logN) time.

1 Like
31

Just remember to set correct upper limit :stuck_out_tongue:

32

Yes, surely i will. :smiley: @vijju123

1 Like
33

j does not get re-initialized every step. Its initialized to 0 only once, and remembers the value of previous iteration. So, once it reaches n, inner loop will never execute. Hence the algo will execute maximum 2n times.

34

Since when we started assuming things, that too on codechef. :slight_smile:
big O is always worst case complexity.

35

Check derivation of “Sieve ofErastothenes” . Its similar to that.

1 Like
36

Theoretically, yes. But the intent of the problem setter to check whether you understand the base of the logarithmic or not :wink:

37

The explanation is correct :slight_smile: But you can explain a bit about harmonic sum and then say that the harmonic sum is bounded by \log{n}, hence, we get an \mathcal{O}(n \log{n}) time algorithm.

38

I am curious as to how to know the complexity of a program, I have binged ( I don’t use google ) the answer, and I found it in several places( SO, wikipedia included ) and I never understand any of the explanation

39

it is n(1+1/2+1/3+1/4+…1/n). The sum in brackets converges to log(n) as n->inf. It is just a known mathematical result.

1 Like
40

Can anyone explain Q20…?