Recent questions tagged time-complexity

int main(){ int c = 0; for(int i = 1; i < n : i++){ for(int j = i + 1; j <= n; j++){ for(int k = 1; k <= j; k++){ c = c + 1; } } } return 0; }What will be the itme comple...

Suppose the running time complexity of EXTRACT-MAX when applied on d-ary heap of height n is Then, the value of x + y + z is ________.Note: d-ary heap can have maximum d...

An algorithm takes as input an nxn Boolean matrix A . If the running time of the algortihm is T(n) = O(nlogn) when n is used as the input size parameter , then which of t...

int fun(int n) { int i, j; for(i=1; i<=n; i++) { for (j=1; j<n; j+=i) { printf("%d %d", i, j); } }}Function_1 while ...

Determine the time complexity of the following loop : for ( int i = 1 ; i <= n ; i++ ) { for ( int j = 1 ; j <= i ; j *= 2) { printf ("Hi") ; } }A. O(n...

What is the Time Complexity of the Dijkstra when it is using Adjacency list + Array (sorted or unsorted ) ? If it is O( V^2 + E ) then ,According to the General form of A...

Let $A[0 \ldots n-1]$ and $B[0 \ldots n-1]$ be two arrays containing $n$ real numbers such that $A[k] \leq A[k+1]$ and $B[k] \leq B[k+1]$ for all $k \in\{0,1, \ldots, n-2...

Even though there are two for loops some times the Time complexity will be the m+n and some times it will be m*n assuming loops run till m and n respectively.How do we di...

Time complexity to find the diameter of a binary tree having $n$ nodes is$O\left(n^{2}\right)$$O(n)$$O(1)$$O(\log n)$

The asymptotic complexity of 4 functions $f_{1}, f_{2}, f_{3}, f_{4}$ are$f_{1}(n)=2^{n}$$f_{2}(n)=n^{(3 / 2)}$$f_{3}(n)=n \log n$$f_{4}(n)=n^{(\log n)}$Arrange them in i...

What is the time complexity of T(n) = T(n/2) + n*(2-cos n)Also try to apply master theorem (Cormen version).

Let $A=\left\{a_{1}, a_{2}, \ldots, a_{n}\right\}$ and $B=\left\{b_{1}, b_{2}, \ldots b_{m}\right\}$ be two sorted arrays of $n$ and $m$ numbers, respectively. Devise an ...

What is the time complexity of code given?def fun(n): count = 0 i = n while i>0 : for j in range(i): count += 1 i //= 2 return count$\Theta(\log n)$$\Theta(n)$$\Theta(n \...

Consider $\text{Iterated logarithm}$ of $n,$ written $\log^\ast n$ (usually read "$\log$ star $n$"), is the number of times the logarithm (base $2$) function must be iter...

Consider the following $\text{C}$ function:def fun1(n): q = 0 for i in range(1, n): p = 0 j = n while j 1: p += 1 j = j // 2 k = 1 while k < p: q += 1 k = k * 2 return q...

What will be the time complexity of following code?def mystery(N): i = 1 s = 1 while s <= N: i += 1 s = s + i$\Theta(\sqrt{N})$$\Theta(N)$$\Theta(\log N)$$\Theta\left((\l...