extract and delete in heap with $O(log n)$

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

I had a test in Algorithms and I had this simple statement which I need to prove/disprove:

"delete and extract in minimum heap operate in $O(n)$"

I wrote that this is not true and it is $O(log n)$. But I think thay tried to misleading me because they wrote $O(n)$ and not $θ(n)$.

The definition of $O(g(n))$ is: all the functions $f(n)$ which there are $c,n_0>0$ that $0leq f(n)le c*g(n)$ for every $n>n_0$.
So extract from a heap is $O(n)$.

What do you think?

algorithms

share|cite|improve this question

edited Jul 18 at 12:59

amWhy

189k25219431

asked Jul 18 at 12:19

joe

546

add a comment | 

up vote
0
down vote

favorite

I had a test in Algorithms and I had this simple statement which I need to prove/disprove:

"delete and extract in minimum heap operate in $O(n)$"

I wrote that this is not true and it is $O(log n)$. But I think thay tried to misleading me because they wrote $O(n)$ and not $θ(n)$.

The definition of $O(g(n))$ is: all the functions $f(n)$ which there are $c,n_0>0$ that $0leq f(n)le c*g(n)$ for every $n>n_0$.
So extract from a heap is $O(n)$.

What do you think?

algorithms

share|cite|improve this question

edited Jul 18 at 12:59

amWhy

189k25219431

asked Jul 18 at 12:19

joe

546

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

I had a test in Algorithms and I had this simple statement which I need to prove/disprove:

"delete and extract in minimum heap operate in $O(n)$"

I wrote that this is not true and it is $O(log n)$. But I think thay tried to misleading me because they wrote $O(n)$ and not $θ(n)$.

The definition of $O(g(n))$ is: all the functions $f(n)$ which there are $c,n_0>0$ that $0leq f(n)le c*g(n)$ for every $n>n_0$.
So extract from a heap is $O(n)$.

What do you think?

algorithms

share|cite|improve this question

edited Jul 18 at 12:59

amWhy

189k25219431

asked Jul 18 at 12:19

joe

546

I had a test in Algorithms and I had this simple statement which I need to prove/disprove:

"delete and extract in minimum heap operate in $O(n)$"

I wrote that this is not true and it is $O(log n)$. But I think thay tried to misleading me because they wrote $O(n)$ and not $θ(n)$.

The definition of $O(g(n))$ is: all the functions $f(n)$ which there are $c,n_0>0$ that $0leq f(n)le c*g(n)$ for every $n>n_0$.
So extract from a heap is $O(n)$.

What do you think?

algorithms

share|cite|improve this question

edited Jul 18 at 12:59

amWhy

189k25219431

asked Jul 18 at 12:19

joe

546

share|cite|improve this question

share|cite|improve this question

edited Jul 18 at 12:59

amWhy

189k25219431

edited Jul 18 at 12:59

amWhy

189k25219431

edited Jul 18 at 12:59

amWhy

189k25219431

189k25219431

asked Jul 18 at 12:19

joe

546

asked Jul 18 at 12:19

joe

546

asked Jul 18 at 12:19

joe

546

546

add a comment | 

add a comment | 

2 Answers
2

active

oldest

votes

up vote
0
down vote



accepted

That's a tough one, because many computer scientists are sloppy, and informally use $O(n)$ to mean $Theta(n)$, or to mean "I think it's $Theta(n)$, but can't really prove it easily, and if it's less than $O(n)$, you're gonna need a better algorithm to demonstrate it."

For a test question, however, I'd say that your second thoughts --- that they're trying to fool you --- are correct. Certainly every function in $O(n mapsto log n)$ is also in $O(n mapsto n)$, so saying that the runtime of delete and extract are in $O(n mapsto n)$ is correct.

share|cite|improve this answer

answered Jul 18 at 12:26

John Hughes

59.4k23785

• 
  
  
  

  
  

  
  
  
  
  
  

  
  thanks! so I also can say that extract is in O(n!)?
  – joe
  Jul 18 at 12:29
  

  
  
  
  

add a comment | 

up vote
1
down vote

A complexity in $O(log n)$ is also in $O(n)$, so that the statement is true. One could add "but this is not tight".

share|cite|improve this answer

answered Jul 18 at 12:47

Yves Daoust

111k665204

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855527%2fextract-and-delete-in-heap-with-o-log-n%23new-answer', 'question_page');

);

Post as a guest

Name Email

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
0
down vote



accepted

That's a tough one, because many computer scientists are sloppy, and informally use $O(n)$ to mean $Theta(n)$, or to mean "I think it's $Theta(n)$, but can't really prove it easily, and if it's less than $O(n)$, you're gonna need a better algorithm to demonstrate it."

For a test question, however, I'd say that your second thoughts --- that they're trying to fool you --- are correct. Certainly every function in $O(n mapsto log n)$ is also in $O(n mapsto n)$, so saying that the runtime of delete and extract are in $O(n mapsto n)$ is correct.

share|cite|improve this answer

answered Jul 18 at 12:26

John Hughes

59.4k23785

• 
  
  
  

  
  

  
  
  
  
  
  

  
  thanks! so I also can say that extract is in O(n!)?
  – joe
  Jul 18 at 12:29
  

  
  
  
  

add a comment | 

up vote
0
down vote



accepted

That's a tough one, because many computer scientists are sloppy, and informally use $O(n)$ to mean $Theta(n)$, or to mean "I think it's $Theta(n)$, but can't really prove it easily, and if it's less than $O(n)$, you're gonna need a better algorithm to demonstrate it."

For a test question, however, I'd say that your second thoughts --- that they're trying to fool you --- are correct. Certainly every function in $O(n mapsto log n)$ is also in $O(n mapsto n)$, so saying that the runtime of delete and extract are in $O(n mapsto n)$ is correct.

share|cite|improve this answer

answered Jul 18 at 12:26

John Hughes

59.4k23785

• 
  
  
  

  
  

  
  
  
  
  
  

  
  thanks! so I also can say that extract is in O(n!)?
  – joe
  Jul 18 at 12:29
  

  
  
  
  

add a comment | 

up vote
0
down vote



accepted

up vote
0
down vote



accepted

That's a tough one, because many computer scientists are sloppy, and informally use $O(n)$ to mean $Theta(n)$, or to mean "I think it's $Theta(n)$, but can't really prove it easily, and if it's less than $O(n)$, you're gonna need a better algorithm to demonstrate it."

For a test question, however, I'd say that your second thoughts --- that they're trying to fool you --- are correct. Certainly every function in $O(n mapsto log n)$ is also in $O(n mapsto n)$, so saying that the runtime of delete and extract are in $O(n mapsto n)$ is correct.

share|cite|improve this answer

answered Jul 18 at 12:26

John Hughes

59.4k23785

That's a tough one, because many computer scientists are sloppy, and informally use $O(n)$ to mean $Theta(n)$, or to mean "I think it's $Theta(n)$, but can't really prove it easily, and if it's less than $O(n)$, you're gonna need a better algorithm to demonstrate it."

For a test question, however, I'd say that your second thoughts --- that they're trying to fool you --- are correct. Certainly every function in $O(n mapsto log n)$ is also in $O(n mapsto n)$, so saying that the runtime of delete and extract are in $O(n mapsto n)$ is correct.

share|cite|improve this answer

answered Jul 18 at 12:26

John Hughes

59.4k23785

share|cite|improve this answer

share|cite|improve this answer

answered Jul 18 at 12:26

John Hughes

59.4k23785

answered Jul 18 at 12:26

John Hughes

59.4k23785

answered Jul 18 at 12:26

John Hughes

59.4k23785

59.4k23785

• 
  
  
  

  
  

  
  
  
  
  
  

  
  thanks! so I also can say that extract is in O(n!)?
  – joe
  Jul 18 at 12:29
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  thanks! so I also can say that extract is in O(n!)?
  – joe
  Jul 18 at 12:29
  

  
  
  
  

thanks! so I also can say that extract is in O(n!)?
– joe
Jul 18 at 12:29

thanks! so I also can say that extract is in O(n!)?
– joe
Jul 18 at 12:29

add a comment | 

up vote
1
down vote

A complexity in $O(log n)$ is also in $O(n)$, so that the statement is true. One could add "but this is not tight".

share|cite|improve this answer

answered Jul 18 at 12:47

Yves Daoust

111k665204

add a comment | 

up vote
1
down vote

A complexity in $O(log n)$ is also in $O(n)$, so that the statement is true. One could add "but this is not tight".

share|cite|improve this answer

answered Jul 18 at 12:47

Yves Daoust

111k665204

add a comment | 

up vote
1
down vote

up vote
1
down vote

A complexity in $O(log n)$ is also in $O(n)$, so that the statement is true. One could add "but this is not tight".

share|cite|improve this answer

answered Jul 18 at 12:47

Yves Daoust

111k665204

A complexity in $O(log n)$ is also in $O(n)$, so that the statement is true. One could add "but this is not tight".

share|cite|improve this answer

answered Jul 18 at 12:47

Yves Daoust

111k665204

share|cite|improve this answer

share|cite|improve this answer

answered Jul 18 at 12:47

Yves Daoust

111k665204

answered Jul 18 at 12:47

Yves Daoust

111k665204

answered Jul 18 at 12:47

Yves Daoust

111k665204

111k665204

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855527%2fextract-and-delete-in-heap-with-o-log-n%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email