Test: Time Complexity- 2 - Computer Science Engineering (CSE) MCQ

may be we have to count those comparisons which results in the execution of loop.

Answer should be Ceil(log₂n) + 1
EDIT: but answer could be: floor(log₂n) + 2

Worst case will arise when both n and m are consecutive Fibonacci numbers.

and n^th Fibonacci number is 1.618ⁿ  where 1.618 is the Golden ratio. 

So, to find gcd(n,m), number of recursive calls will be θ(logn)

Worst Case : 

Best Case : When n is an even number body of for loop is executed only 1 time (due to "return 0" inside if) which is  irrespective of 

We need to divide
n recursively and compute like following:

  In this, we need to calculate b^n/2 only once.

.

.

Recurrence relation: 

Gradient = y₂-y₁/x₂-x₁

For gradient to be maximum x₂-x₁ should be minimum. So, sort the points (in θ(nlogn) time) according to x coordinate and find the minimum difference between them (in θ(n) time).

Best complexity: θ(nlogn + n) which leads to B.

whenever there exists an element which is present in the array : more than n/2 times, then definitely it will be present at the middle index position; in addition to that it will also be present at anyone of the neighbourhood indices namely i - 1 and i + 1 

No matter how we push that stream of More than n/2 times of elements of same value around the Sorted Array, it is bound to be present at the middle index + atleast anyone of its neighbourhood once we got the element which should have occurred more that n/2 times.we count its total occurrences in O(logn) time. 

To check whether a given number is repeated n/2 times in the array can be done in O(log n) time.

Algo

1. find the first occurrence (index i) of x(given number) in the array which can be done in O(log n) time (a variant of binary search).

2. check if A[i] == A[n/2+i]

return true
3. else return false

Total number of multiplications

The operations given can be performed in any order. So, for Min-heap we cannot do the usual BuildHeap method.

Delete in unsorted array is O(1) as we can just swap the deleted element with the last element in the array and delete the last element.

For sorted-doubly linked-list we cannot do binary search as this would require another array to maintain the pointers to the
nodes.

According to the recurrrence relation

T(n) = 2 T( n-1 ) +1

Tower of hanoi we get it is Ɵ(2ⁿ)
now heap sort worst case Ɵ(n log n)

Binary Search given n numbers n sorted numbers Ɵ(log n)
Addition of two nxn matrices Ɵ (n²)
so C is correct answer here

inner for loop is dependent on i, so for each i we have to check no of times inner loop operating..

it ll be something like

1) Calculate the medians m1 and m2 of the input arrays ar1[]
and ar2[] respectively.
2) If m1 and m2 both are equal.
return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
of the below two subarrays.
a) From first element of ar1 to m1 (ar1[0 to n/2])
b) From m2 to last element of ar2 (ar2[n/2 to n-1])
4) If m2 is greater than m1, then median is present in one
of the below two subarrays.
a) From m1 to last element of ar1 (ar1[n/2 to n-1])
b) From first element of ar2 to m2 (ar2[0 to n/2])
5) Repeat the above process until size of both the subarrays
becomes 2.

6) If size of the two arrays is 2 then
the median.
Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
Time complexity O(logn)

Let us take log for each function.

Here, If we consider logn as a term (which is common in all 3), first 1 is a log function, second one is sqrt function and third one is linear function of logn . Order of growth of these functions are well known and log is the slowest growing followed by sqrt and then linear. So, option A is the correct answer here. 

PS: After taking log is we arrive at functions distinguished by some constant terms only, then we can not conclude the order of grpwth of the original functions using the log function. Examples are 

it is fibanacci series generation. it takes exponential time if we won't use dynamic programming.
if we use dynamic programming then it takes O(n)

Trying the values, 5 doesn't satisfy this but 6 satisfies.