Dark Mode

Recent questions tagged time-complexity

0 votes

1 answer

1

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

Çșȇ ʛấẗẻ asked in Algorithms Mar 14

by Çșȇ ʛấẗẻ

97 views

0 votes

2 answers

2

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

ahmed malik asked in Algorithms Mar 5

94 views

1 vote

1 answer

3

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))$.

admin asked in DS Feb 15

by admin

983 views

0 votes

0 answers

4

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))$

GO Classes asked in Algorithms Feb 6

548 views

0 votes

1 answer

5

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 asked in Algorithms Jan 18

by soukL

164 views

0 votes

0 answers

6

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?

kira000 asked in Algorithms Jan 17

131 views

0 votes

0 answers

7

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

MonuKhan asked in Algorithms Jan 12

289 views

2 votes

1 answer

8

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

h4kr asked in Algorithms Dec 30, 2022

by h4kr

189 views

0 votes

1 answer

9

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$)

Souvik33 asked in DS Dec 17, 2022

267 views

1 vote

0 answers

10

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).

admin asked in Algorithms Dec 15, 2022

by admin

58 views

0 votes

1 answer

11

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

shub2204 asked in DS Dec 5, 2022

292 views

1 vote

1 answer

12

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

jola asked in Algorithms Dec 5, 2022

by jola

137 views

1 vote

2 answers

13

#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?

Dknights asked in Programming Nov 29, 2022

99 views

0 votes

1 answer

14

#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)

Dknights asked in Algorithms Nov 23, 2022

140 views

0 votes

1 answer

15

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

Chaitanya Kale asked in Algorithms Nov 10, 2022

by Chaitanya Kale

159 views

Page:

1
2
3
4
5
6
...
50
next »

Recent questions tagged time-complexity