Recent questions tagged time-complexity

Someone help with this...I am getting option-b but key is opt-aa)b)c)d)

You were given an array of distinct elements of size n with indices starting from 0.-Every $(2i)^{th}$ element is pushed into a stack.-Every $(2i+1)^{th}$ element is enqu...

What is the complexity of the following using Big O:

Match the LIST-I with LIST-II$\begin{array}{|l|l|l|l|} \hline & \textbf{LIST-I} & & \textbf{LIST-II} \\ & \textbf{Algorithm} & & \textbf{Complexity} \\ \hline \text{A.}...

Arrange the following recurrence relations in increasing order of their time capacity.$\mathrm{T}(\mathrm{n})=\mathrm{T}(\mathrm{n} / 2)+1$$\mathrm{T}(\mathrm{n})=2 \math...

Match List - I with List - II.$\begin{array}{llll} & \textbf{List - I} & & \textbf{List-II} \\ & \textbf{(Recurrence Relations)} && \textbf{(Complexity)} \\ \text{(A)}& \...

Which of the following is $\text{TRUE}?$The cost of searching an AVL tree is $\theta(\log n)$ but that of binary search is $0(n)$The cost of searching an AVL tree in $\th...

We have an array $A$ of $n$ numbers, where $n$ is a power of $2$.We build a full binary tree on top of the array $A.$ The elements of the array are leaves of the tree, nu...

We have an array $A$ of $n$ numbers, where $n$ is a power of $2$.We build a full binary tree on top of the array $A.$ The elements of the array are leaves of the tree, nu...

Which of the following operations can be performed in $\mathrm{O}(\log n)$ time in a binary heap?Deleting the root elementInserting an elementBoth $\text{(A)}$ and $\text...

Which of the following is the correct asymptotic notation for an algorithm that grows slower than $\text{O}\left(n^{\wedge} 2\right)$ but faster than $\text{O}(n)?$$\text...

We have an array $A$ of $n$ numbers, where $n$ is a power of $2$.We build a full binary tree on top of the array $A.$ The elements of the array are leaves of the tree, nu...

The next two questions pertain to the following code which takes a non-negative integer as input}.function FOO(n) if (n=0) then return 0 else if (n=1) then return 1 else ...

What is the solution to the following recursion?$$\begin{array}{l}T(n)=T\left(\dfrac{n}{2}\right)+T\left(\dfrac{n}{3}\right)+T\left(\dfrac{n}{6}\right)+O(n), \\T(n)=5 \qu...

Recall the insertion sort algorithm: procedure INSERTIONSORT(A) for i ← 1 to A.length - 1 do key ← A[i] j ← i - 1 while j ≥ 0 and A[j] key do A[j + ...

Given an array $A=\left(a_{0}, a_{1}, \ldots, a_{n-1}\right)$ of integers, your task is to determine the maximum possible sum\[\operatorname{maxsum}(A)=\max _{0 \leq s \l...

Let $R$ be the root of a balanced binary search tree having $n$ nodes, where each node contains an integer, a pointer to its left child and a pointer to its right child. ...

For functions $f, g: \mathbb{N} \rightarrow \mathbb{R}$, we say that $f$ is $o(g)$ (in words, $f$ is $little-oh$ of $g$ ) if $\lim _{n \rightarrow \infty} \frac{f(n)}{g(...