Recent questions tagged time-complexity / GATE Overflow for GATE CSE

3 votes

0 answers

91

GO Classes 2023 | IIITH Mock Test 1 | Question: 13
Arrange the following functions in their increasing order of growth. In options $\log ^{2} n$ means $(\log n)^{2}$ $\log (n !), \log ^{2} n, (\lg n) !, e^{n}$ $\log (n !), \log ^{2} n, e^{n}, (\lg n) !$ $\log ^{2} n, \log (n !), (\lg n) !, e^{n}$ $\log ^{2} n, (\lg n) !, \log (n !), e^{n}$

Arrange the following functions in their increasing order of growth. In options $\log ^{2} n$ means $(\log n)^{2}$$\log (n !), \log ^{2} n, (\lg n) !, e^{n}$$\log (n !)...

GO Classes

660 views

GO Classes asked Mar 26, 2023

2 votes

1 answer

92

GO Classes 2023 | IIITH Mock Test 1 | Question: 45
Assume you have two positive functions $f$ and $g$ such that $f(n)$ is in $O(g(n))$. For each of the following statements, decide which one(s) is/are always TRUE. $2^{f(n)}$ is $O\left(2^{g(n)}\right)$ $f(n)^{2}$ is $O\left(g(n)^{2}\right)$ $f(n)=O\left((f(n))^{2}\right)$ $g(n)=\Omega(g(n))$

Assume you have two positive functions $f$ and $g$ such that $f(n)$ is in $O(g(n))$. For each of the following statements, decide which one(s) is/are always TRUE.$2^{f(n)...

GO Classes

823 views

GO Classes asked Mar 26, 2023

0 votes

1 answer

93

self doubt
Solve the following recurrences using recursion tree method and write the asymptotic time complexity T(n)=T(n/2)+n^2

Solve the following recurrences using recursion tree method and write the asymptotic time complexity T(n)=T(n/2)+n^2

Çșȇ ʛấẗẻ

423 views

Çșȇ ʛấẗẻ asked Mar 14, 2023

3 votes

1 answer

94

TIFR CSE 2023 | Part B | Question: 6
What is the solution to the following recurrence? \[ T(n)=\left\{\begin{array}{ll} 1 & \text { if } n \leq 10, \\ \sqrt{n} \cdot T(\sqrt{n})+n & \text { if } n>10. \end{array}\right. \] $T(n)=\Theta\left(n^{2}\right)$ $T(n)=\Theta(n \log n)$ $T(n)=\Theta(n \sqrt{\log n})$ $T(n)=\Theta(n \log \log n)$ None of the above

What is the solution to the following recurrence?\[T(n)=\left\{\begin{array}{ll}1 & \text { if } n \leq 10, \\\sqrt{n} \cdot T(\sqrt{n})+n & \text { if } n>10.\end{array}...

admin

578 views

admin asked Mar 14, 2023

1 votes

2 answers

95

Chose the correct big- Θ expression to describe: T(N) = T(N / 2) + Log(N/2); T(1) = 1
I

I

ahmed malik

445 views

ahmed malik asked Mar 4, 2023

7 votes

3 answers

96

GATE CSE 2023 | Question: 36
Let $A$ be a priority queue for maintaining a set of elements. Suppose $A$ is implemented using a max-heap data structure. The operation $\text{EXTRACT-MAX} (A)$ extracts and deletes the maximum element from $A$. The operation $\operatorname{INSERT}(A, key )$ inserts a new ... $O(1)$ whereas $\operatorname{INSERT}(A, k e y)$ runs in $O(\log (n))$.

Let $A$ be a priority queue for maintaining a set of elements. Suppose $A$ is implemented using a max-heap data structure. The operation $\text{EXTRACT-MAX} (A)$ extracts...

admin

6.2k views

admin asked Feb 15, 2023

0 votes

0 answers

97

GATE CSE 2023 | Memory Based Question: 37
Time complexity f( ) { while(n>1) { for (i = 1 to n) { } n = n/2 } } g ( ) { for (i = 1 to 100n) { } } $f(x)=O(g(x))$ $f(x)=\theta(g(x))$ $f(x)=o(g(x))$ $f(x)=\omega(g(x))$

Time complexity f( ) { while(n>1) { for (i = 1 to n) { } n = n/2 } } g ( ) { for (i = 1 to 100n) { } } $f(x)...

GO Classes

1.4k views

GO Classes asked Feb 5, 2023

0 votes

1 answer

98

let T(n) a function of complexity satisfying T(0)=T(1)=Θ(1) and T(n)=Θ(n)+T(n−1)+T(n−2). what is the class of complexity of T(n) ?

soukL

412 views

soukL asked Jan 17, 2023

0 votes

0 answers

99

Asymptotic Notation
Let $f(n)$ be a positive increasing function. Consider the below two statements: S1: if an algorithm is $\Theta(f(n))$ in the average case, then it is $\Omega(f(n))$ in the worst case. S2: if an algorithm is $\Theta(f(n))$ in the average case, then it is ... understand it mathematically. Also, $g(n) = \Theta(f(n))$ actually means $g(n)$ belongs to the set $\Theta(f(n))$, right?

Let $f(n)$ be a positive increasing function. Consider the below two statements:S1: if an algorithm is $\Theta(f(n))$ in the average case, then it is $\Omega(f(n))$ in th...

kira000

486 views

kira000 asked Jan 17, 2023

1 votes

0 answers

100

Test series
Can anyone solve this recurrence relation T(n) = 3T(n-1) + O(n^2) Its ans is O(3^n n^2)

Can anyone solve this recurrence relation T(n) = 3T(n-1) + O(n^2)Its ans is O(3^n n^2)

MonuKhan

614 views

MonuKhan asked Jan 12, 2023

2 votes

1 answer

101

What is time complexity?
What is the correct time complexity in $\theta()$ ?

What is the correct time complexity in $\theta()$ ?

h4kr

465 views

h4kr asked Dec 30, 2022

1 votes

1 answer

102

Array P&DS | Time Complexity
What is the worst case time complexity of an efficient algorithm (in order of n) to get the last index for an actually filled element, in an array, given the condition that we may not fill the entire initialized array with elements, the array is initialized as “int a[n]; ” [Array may not be filled in a sorted order] O(n) O(1) O(log(n)) O($n^2$)

What is the worst case time complexity of an efficient algorithm (in order of n) to get the last index for an actually filled element, in an array, given the condition th...

Souvik33

667 views

Souvik33 asked Dec 17, 2022

1 votes

0 answers

103

DRDO CSE 2022 Paper 1 | Question: 32 (b)
Let us suppose we are given an integer $\text{N}$ in binary representation. Let us consider the following algorithm to check if $\text{N}$ is a prime. For every $i$ such that $2 \leq i \leq\lceil\sqrt{\text{N}}\rceil$ ... of the running time in terms of the input size? (Assume hypothetically that division can be done in $\text{O}(1)$ time).

Let us suppose we are given an integer $\text{N}$ in binary representation. Let us consider the following algorithm to check if $\text{N}$ is a prime.For every $i$ such t...

admin

228 views

admin asked Dec 15, 2022

0 votes

1 answer

104

DSA
Given two max heap, one of size n and other m. Calculate the time complexity of merging them to get a max heap.

Given two max heap, one of size n and other m. Calculate the time complexity of merging them to get a max heap.

shub2204

885 views

shub2204 asked Dec 5, 2022

1 votes

1 answer

105

CS Data structures and algorithm 2022
Design an algorithm to construct one heap that contains all the elements of two given heaps of sizes n and m, respectively. The heaps are given in a linked-list representation ( each node has links to its two children). The running time of the algorithm should be O(log(m + n)) in the worst case

Design an algorithm to construct one heap that contains all the elements of two given heaps of sizes n and m, respectively. The heaps are given in a linked-list represent...

jola

423 views

jola asked Dec 5, 2022

1 votes

2 answers

106

#self_doubt
what if a full binary tree contains both left and right sides as the max heap, then what will be the complexity of making it a proper max heap?

what if a full binary tree contains both left and right sides as the max heap, then what will be the complexity of making it a proper max heap?

Dknights

511 views

Dknights asked Nov 29, 2022

0 votes

1 answer

107

#self_doubt
T(n)={ 0:if n<1 1:if n==1 T(n-1)+T(n-2):n>1 } if the stack size is 48 bytes and one stack entry size =4 B then maximum n=? I thought it should be 13 but the answer is 12 T(1) and T(<1) should not be stored they are already given so can we take n=13 so the last call which will be stored will be T(2)

T(n)={0:if n<11:if n==1T(n-1)+T(n-2):n>1}if the stack size is 48 bytes and one stack entry size =4 B then maximum n=?I thought it should be 13 but the answer is 12T(1) an...

Dknights

391 views

Dknights asked Nov 23, 2022

0 votes

1 answer

108

Asymptotic notations
Can we write f(2$^{n/a}$) = Θ(2$^{n}$) for any integer a >0?

Can we write f(2$^{n/a}$) = Θ(2$^{n}$) for any integer a >0?

Chaitanya Kale

294 views

Chaitanya Kale asked Nov 10, 2022

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true